ОСНОВЫ МАТEМАТИЧEСКОЙ ЛОГИКИ 2

0
1
1
0
1
0 1
1
0
0
0
0
0
0 1
1
0
1
1
0
1
0 0
0
1
1
1
1
0
0 0
0
0
1
1
0
0
0 1
1
1
1
0
1
1
1
Построение таблиц истинности для различных формул и сравнение этих таблиц всегда дает возможность установить: являются ли рассматриваемые формулы равносильными? Однако, такой метод требует 2*2^n вычислений (если считать, что обе формулы зависят от n переменных) и на практике оказывается слишком громоздким. Поэтому для установления равносильности формул, преобразования и получения новых формул целесообразнее пользоваться законами и тождествами алгебры логики, в справедливости которых можно убедиться с помощью таблиц истинности.
Формула, которая истинна (принимает значение "1") при любых истинностных значениях ее аргументов, называется тождественно истинной формулой или тавтологией. Примером тавтологии может служить высказывание "Если внедрить новую технологию (P), то качество продукции улучшится (Q). При улучшении качества продукции (Q) ее сбыт увеличивается (R). Новая технология внедрена (P). Следовательно, сбыт продукции увеличился (Я)".
Это высказывание выражается формулой
(P ? Q)(Q ? R)*P? R.
Чтобы убедиться, что данная формула является тавтологией можно составить для нее истинностную таблицу:

P
Q
R 0
0
0
0
1 0
1
0 0
1
1 1
0
0 1
0
1 1
1
0 1
1
1
P ? Q
Q ? R
(P ? Q)(Q ? R)*P
(P ? Q)(Q ? R)*P? R 1
1
0
1 1
1
0
1 1
0
0
1 1
1
0
1 0
1
0
1 0
1
0
1 1
0
0
1 1
1
1
1
Различные подстановки в тавтологию, независимо от их конкретного содержания, всегда являются истинными высказываниями в силу одной только своей логической структуры. Иначе говоря, тавтологию можно рассматривать как некоторые логические схемы рассуждений или утверждений. Поэтому тавтологии играют роль законов (теории) логики высказываний, претендующих на установление методов построения правильных умозаключений. Формула не является тавтологией, если она принимает значение "0" хотя бы на одном наборе значений переменных.
Формула, которая ложна (принимает значение "0") при всех возможных истинностных значениях ее аргументов, называется тождественно ложной или противоречием. Примерами противоречий являются х — = х, х*х.
Рассмотрим некоторые правила образования тавтологий и противоречий:
1. Логическое произведение двух различных членов формулы, содержащих конъюнкции т аргументов, является противоречием (тождественно равно "0") тогда и только тогда, когда один из членов формулы включает отрицание хотя бы одного из аргументов, входящих в другой конъюнктивный член. Например
(x1*x2*x3)*(x1*x2*x3) ? 0.
2. Логическая сумма двух различных членов формулы, содержащих дизъюнкции т аргументов, является тавтологией тогда и только тогда, когда один из указанных членов содержит отрицание хотя бы одного из аргументов. Например
(x1 v x2 v x3) v (x4 v x5 v x6)
Для решения ряда принципиальных вопросов, связанных с теорией функций алгебры логики и с практическим применением результатов этой теории для анализа и синтеза схем, полезно использовать основные классы функций алгебры логики.
В качестве первого класса таких функций рассмотрим класс функций, сохраняющих константу нуль (противоречие), то есть таких функций, для которых имеет место равенство
f(0,0,…0) = 0.
Этот класс функций обозначают буквой К0. Очевидно, что при фиксированном и число функций этого класса составляет половину всех функций алгебры логики, то есть 2^(2^(n-1)) функций.
Аналогично класс функций, сохраняющих константу единица (тавтология), может быть определен как класс функций, для которых имеет место равенство
f(1,1,…1) = 1
Этот класс, состоящий также из 2^(2^(n-1)) функций, обозначают символом К1 .
Функция f(х1,…, хn) называется симметричной, если она изменяется при произвольной перенумерации аргументов:
f(х1,…, хn) = f(y1,…,yn),
где (y1,…,yn) — любая перестановка аргументов (х1,…, хn).
Класс таких функций обозначают буквой S [5].
Произвольная логическая функция может быть задана одним из трех способов: матричным (табличным), геометрическим или аналитическим.
При матричном способе функция задается таблицей истинности, в левой части которой представлены все возможные двоичные наборы переменных, а в правой указывается значение функции на этих наборах. Логические функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности функции восьми переменных будет содержать 2^8 = 256 строк.
При геометрическом способе логическая функция может быть задана с помощью и -мерного куба.
При аналитическом способе логическая функция задается формулами, то есть аналитическими выражениями, построенными на основе логических операций. Аналитический способ задания функций занимает особое место в виду возможности выполнения преобразований логических формул.
Представление одних элементарных функций через другие
Логические функции можно преобразовывать из одного вида в другой. Эквивалентные преобразования в аналитической форме являются мощным средством доказательства равносильности функций, как правило, более эффективным, чем их вычисления в истинностных таблицах на наборах значений переменных.
Путем составления и сравнения таблиц истинности установлены ряд формул, которые отражают основные свойства, законы и тождества логических функций и широко применяются для аналитических преобразований логических формул.
Закон снятия двойного отрицания
x ? х (2.1)
Свойства отрицания:
x v х ?1 (2.2)
x * х ?0 (2.3)
Свойства констант:
x * 0 ?0 (2.4)
x * 1? х (2.5)
x v 0 ?x (2.6)
x v 1 ?1 (2.6)
Законы идемпотентности:
x * х ?0 (2.8)
x v x =х (2.9)
Свойства коммутативности (переместительный закон):
x1 *x2 ? x1 * x2 (2.10)
x1 v x2? x1 v x2 (2.11)
Свойства ассоциативности (сочетательный закон):
x1 *(x2* x3 )? (x1* x2 )*x3 (2.12)
x1 v (x1* x2 )? (x1 v x2 ) v x3 (2.13)
Свойства дистрибутивности (распределительный закон):
x1 *(x2 v x3 ) ? (x1* x2 ) v (x1* x3 ) (2.14)
x1 v(x2 * x3 ) ? (x1 v x2 )*(x1 v x3 ) (2.15)
Свойства "поглощения":

x1 *(x1 v x2 ) ?x1 (2.16)
x1 v(x1 * x2) ?x1 (2.17)
Свойства "склеивания":
(x1* x2 ) v (x1* x2 ) ? x1 (2.18)
(x1 v x2 )*(x1 v x2 ) ? x1 (2.19)
Законы де Моргана:
x1 v x2 ? x1* x2 (2.20)
x1* x2 ? x1 v x2 (2.21)
Закон противоречия
x1* x2 ? 1 (2.22)
вытекает из (2.21) н (2.2).
Как следствие из (2.8) и (2.9) получаем тождества:
x*х*…*х ? х;
x v x v... v x ? x
Законы де Моргана могут быть представлены в виде:

x1 * x2*...* xn ?x1 v x2 v …v xn

x1 v x2v...v xn ?x1 v x2 v …v xn
Из таблиц истинности справедливы соотношения:
x1 ? x2 ? x1 v x2 (2.23)
x1 ~ x2 ? x1 0 x2 (2.24)
x1 ~ x2 ? ( x1 v x2)(х1 v x2) (2.25)
Закон тождества
x ? x ? 1 (2.26)
Закон двойного отрицания
x ~ x ? 1 (2.27)
Добавление антецедента ("истина из чего угодно")
x1 ?( x2 ? x1) ? 1 (2.28)
"Из ложного что угодно"
x1 ?(x1 ? x2 )? 1 (2.29)
Закон отделения (modus ponens)
x1 * (x1 ? x2 ) ? x2 ? 1 (2.30)
Modus tollens
(x1 ? x2 ) * x2 ? x1 ? 1 (2.31)
Закон силлогизма
((x1 ? x2 )* (x2? x3 )) ? (x1 ? x3 )? 1 (2.32)
Закон контрапозиции
(x1 ? x2 ) ? (x2? x1 ) ? 1 (2.33)
Свойства функции сложения по модулю 2 и функции импликации часто бывают полезными при анализе и синтезе различных дискретных устройств.
Для функции сложения по модулю 2 имеют место переместительный и сочетательный законы, а также распределительный закон относительно конъюнкции:
x1 x2 ? x2 x1;
x1 ( x2 x3 ) ? (x1 x2 ) x3 ;
x1 & ( x2 x3 ) ? (x1 & x2 ) (x1 & x3 ).

Имеют место также соотношения:
x x ?0
x 0 ? x (2.34)
x 1 ? x
x x ?0
Кроме того, имеет место формула
x1 v x2 ? x1 x2 x1 x2. (2.35)
В отличие от ранее рассмотренных функций для импликации не имеют места переместительный и сочетательный законы:
x ? x ?1
x ? x ? x
x ?1 ? 1 (2.36)
x ?0 ? x
0 ? x ?1
1 ? x ?x
x1 ? x2 ? x2 ? x1
x1 ? x2 ? x1 ? x1
Функции дизъюнкции и конъюнкции могут быть выражены через импликацию следующим образом:
x1 v x2 ? x1 ? x2 ;
x1 x2 ? x1 ? x2 (2.37)
Для функций Шеффера и Вебба имеет место переместительный закон
x1 ? x2 ? x2 ? x1 ;
x1 ? x2 ? x2 ? x1 ;
Сочетательный закон для них несправедлив:
x1 ?( x ? x3 ) ? (x1 ? x2 ) ? x3 ;
x1? ( x2 ? x3 ) ? (x1? x2 ) ? x3/
Имеют место следующие очевидные соотношения:

x ? x ? x x ? x ?x
x ? x ? 1 x ? x ?0
x ?1 ? x x ? 1 ?x (2.38)
x ?0 ? x x ? 0 ?x
x1 ? x1 x2 ? x1 v x2
x1? x2 ? x1 v x2 ? x1 x2
В силу отсутствия сочетательного закона, действия раскрытия скобок и вынесения за скобки для функций Шеффера и Вебба специфичны, и выполняются по следующим правилам:

(x1 ? x2 )? (x1 ? x3 ) ? x1 ?( x2 ? x3 ) ? x1 ? (x2 ? x3);
(x1 ? x2 ) ? (x1 ? x3 ) ? x1 ? ( x2 ? x3 ) ? x1 ? (x2 ? x3);

(x1 ? x2 ) ? (x1 ? x3 ) ? x1 ?( x2 ? x3 ) ? x1 ? (x2 ? x3);
(2.38)
x1 ? x2 ) ? (x1 ? x3 ) ? x1 ? ( x2 ? x3 ) ? x1 ? (x2?x3);

(x1 ? x2 ) ? (x3 ? x4 ) ? x1 ? x2 ? x3 ? x4;

(x1 ? x2 ) ? (x3 ? x4 ) ? x1 ? x2 ? x3 ? x4.
Докажем, например, справедливость равенства
(x1 ? x2 ) ? (x1 ? x3 ) ? x1 ? ( x2 ? x3 )
Используя два последних соотношения из (2.38), преобразуем обе части этого соотношения следующим образом:
(x1 ? x2 ) ? (x1 ? x3 ) ? x1 v x2 ? x1 v x3 ?(x1 v x2 )v (x1 v x3 ) ? x1 vx2 vx3
x1 ?( x2 ? x3 ) ? x1 v ( x2 ? x3 )? x1v (x2 v x3 ) ? x1 v x2 v x3
Совпадение левой и правой частей после проведения эквивалентных преобразований доказывает равенство.
Функции Шеффера и Вебба связаны между собой соотношениями, аналогичными формулам де Моргана для функций конъюнкции и дизъюнкции:
x1 ? x2 ? x1 ? x2 ?x
x1 ? x 2? x 1 ? x2 (2.40)
Для доказательства справедливости первого из этих соотношений заметим, что на основании двух последних равенств из (2.38) можно первое из соотношений (2.40) переписать в следующем виде:
x1 x2? x1 v x2
x1 x2? x1 v x2
Так как полученное соотношение есть формула де Моргана, то первое из соотношений справедливо. Для второго соотношения доказательство аналогично.

Булева алгебра
Любая формула, образованная из n элементов (переменных), порождает логическую функцию, но не любая логическая функция может быть выражена формулой. Все зависит от того, какие логические операции используются для построения данной формулы.
Если данная совокупность логических операций достаточна, чтобы любую логическую функцию выразить формулой, то такая совокупность операций называется функционально полной. Строго доказано, что совокупность операций &, v, (инверсии, конъюнкции и дизъюнкции) является функционально полной системой логических операций. Это означает, что любую формулу, содержащую любые логические операции, можно путем равносильных преобразований привести к виду формулы, содержащей лишь операции &, v.
Если сама функция, зависящая от n переменных, и любой из ее аргументов принимают значения только из множества {О, 1}, то ее называют булевой функцией. Аргументы булевой функции также называются булевыми.
Множество всех булевых функций вместе с операциями инверсии, конъюнкции и дизъюнкции образуют булеву алгебру.
Операции &, v удовлетворяют соотношениям (2.1) - (2.22) и называются операциями булевой алгебры.
Логические операции не являются независимыми и одни из них могут
быть выражены через другие. Так, всякая формула, содержащая любые логические операции, с помощью тождественных равенств (2.23) - (2.38) может быть приведена к виду, содержащему только операции булевой алгебры. Используя равносильности закона де Моргана и закона снятия двойного отрицания можно дизъюнкцию выразить через конъюнкцию и отрицание, и наоборот, конъюнкцию — через дизъюнкцию и отрицание. Таким образом, всякую формулу алгебры логики можно заменить на равносильную ей и содержащую символы операций и, &, (или и v).
В свою очередь каждая из операций "штрих Шеффера" и "стрелка Пирса" образует функционально полную систему логических операций, а значит любую формулу алгебры логики можно преобразовать в равносильную ей формулу, записанную только с помощью операций "штрих Шеффера" (или только "стрелка Пирса").Функционально полные наборы булевых функций приведены в табл.А.1 Приложения А. Возникает вопрос: если все логические операции могут быть сведены к трем (], &, v), или к двум (], v), или даже только к одной (? или ?) операции, то зачем же в логике высказываний и алгебре логики введены другие операции'? Ответ заключается в следующем.
1. Для обозримости и удобочитаемости формул.
2. Каждая из рассмотренных операций играет определенную роль при описании закономерностей логических заключений. Особенно это относится к операции "импликация".
3. Логика высказываний — самый элементарный раздел математической логики. В других ее разделах (исчисление высказываний, строгой импликации и др.) не всегда допускается выражение одних операций через другие.
4. В средствах вычислительной техники можно строить более компактные схемы, используя логические элементы, реализующие, например, операции неравнозначности (сумматор по модулю 2), эквивалентности вместо элементарных логических элементов: инвертора, конъюнктора и дизъюнктора.
Наибольшее развитие и законченность изучения, вследствие своей простоты и широкого практического применения, получила булева алгебра. Ее аппарат сегодня является основой современной цифровой вычислительной техники и устройств с программным управлением. При этом приведенные ранее свойства, законы и тождества алгебры логики остаются справедливыми и для преобразования формул булевой алгебры с применением подстановок и замен переменных. В булевой алгебре приняты следующие упрощения записи формул:
1. Если переменные или формулы связаны только посредством одной из операций дизъюнкции (или конъюнкции), то их можно выполнять в любом порядке, а формулы записывать без скобок.
2. При наличии скобок в формуле в первую очередь должны выполняться операции внутри скобок.
3. Считают, что операция конъюнкции должна предшествовать операции дизъюнкции, поэтому можно опускать скобки, в которые заключены формулы со знаком конъюнкции.
4. Обычно опускают скобки, если они являются внешними скобками у конъюнкции.
5. Принято опускать скобки, в которые заключены формулы со знаком отрицания.
6. Знак конъюнкции в формулах можно опустить и вместо (x & y) или (х ? у) писать ху.
С учетом приведенных условий запись существенно упрощается. Например, формуле (х ? (у ? z)) v ((x v y) ? z) соответствует запись
хуz v х v у*z; вместо (х1(х2 v xз)) v (x4x5) пишут х1(х2 v xз) v x4x5..
Пользуясь свойствами, законами и равносильностями алгебры логики всякую формулу можно преобразовать, приводя ее к тому или иному виду.
С целью улучшения обозримости и применения, а также облегчения подбора для преобразований основные законы, свойства и тождества алгебры логики выбраны и сконцентрированы в едином перечне, приведённом в Приложении Б. Тождествам в перечне присвоены порядковые номера, которые будут использоваться в ссылках при дальнейшем изложении материала.
Когда считать, что преобразования формулы завершены? Это зависит в каждом конкретном случае от цели, которая ставится и должна быть достигнута. Для технической реализации в электрических цепях, электронной технике, системах управления, наиболее удобно всякую формулу алгебры логики выразить через операции булевой алгебры, а затем привести к некоторой "стандартной", так называемой нормальной форме.

Формы представления логических функций
Конъюнкция х1 * x2 *...*хn , называется элементарной если в этой конъюнкции каждая переменная (или ее отрицание) встречается не более одного раза.
Рангом элементарной конъюнкции называется число букв, образующих эту конъюнкцию
Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).
Свойства обобщенного склеивания (18) и поглощения (16), (17) показывают, что ДНФ функции может быть не единственной. Например:
xz v y z v xy ? xz v уz v xyz v x y z ? xz v xyz v y z v xyz ? хz (1 v y) v
v уz (1 v х) ? xz v у z .
Длиной ДНФ называют число элементарных конъюнкций, образующих эту ДНФ.
Дизъюнктивная нормальная форма, имеющая наименьшую длину по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется кратчайшей ДНФ (КДНФ).
Дизъюнктивная нормальная форма, содержащая наименьшее число букв хi,. по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется минимальной ДНФ (МДНФ).
Дизъюнктивная нормальная форма для функции f (х1,х2,…, xn), состоящая из элементарных конъюнкций ранга и, называется совершенной дизъюнктивной нормальной формой (СДНФ). В СДНФ входят конъюнкции наибольшего возможного для данной функции ранга.
Аналогичные определения можно дать и для случая конъюнктивных нормальных форм.
Конъюнкция элементарных дизъюнкции называется конъюнктивной
нормальной формой (КНФ). Например:
ху v xy v x z ? ху v xy v xz ? (x v y)(x v y)(x v z) ? ху v xyz v xyz ?

? xy v xyz ? (x v y)( x v y v z).
КНФ для функции f(x1,x2,...,хn), состоящая из элементарных дизъюнкций ранга и, называется совершенной конъюнктивной нормальной формой (СКНФ).
Любая булева функция не являющаяся противоречием (тождественным
нулем) или тавтологией имеет одну и только одну СДНФ или СКНФ. Напри-
мер:
x y z v x z ? x y z v x z (y v y) ? xyz v x y z v xyz — СДНФ;
х(у v z)(хv z)? (х v уу)(у v z v х х)(х v z v у у) ? (х v у)(х v у)(у v z v х).
( y v z v x)(x v y v z)(x v z v y)? (хv у v zz)(х v у v zz)(х v у v z)( х v у v z).

<< Пред. стр. 2 (из 7) След. >>

Список литературы по разделу