Функционально полные системы логических функций. Алгебраический подход

                                                       4

  Таким образом,  конъюнкцией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания А и В.

  Конъюнкцию высказываний А и В мы обозначим: A & B. Знак & - амперсент - читается как английское "and" (помните Procter & Gamble или Wash & Go?). Часто встречается обозначение А Λ В. Иногда, для краткости, пишут просто АВ.

Определение конъюнкции может быть записано в виде таблицы  истинности, в которой для каждого  из четырех возможных наборов  значений исходных высказываний А и В задается соответствующее значение конъюнкции А & В:

 

Определение конъюнкции двух высказываний естественным образом  распространяется на любое конечное число составляющих: конъюнкция А1 & A2 & A3 &...& AN истинна тогда и только тогда, когда истинны все высказывания А1, A2, A3, ...AN (а, следовательно, ложна, когда ложно хотя бы одно из этих высказываний).

     Логическое  сложение (дизъюнкция) от латинского disjunctio - разобщение, различие.

     Если  два высказывания соединены союзом "ИЛИ", то полученное сложное  высказывание обычно считается  истинным, когда истинно хотя бы одно из составляющих высказываний. Например, возьмем два высказывания: "Мел черный." (А), "Доска черная." (В). Высказывание "Мел черный или доска черная" будет истинным, т.к. одно из исходных высказываний (В) истинно.

     Таким  образом, дизъюнкцией двух высказываний  называется такое новое высказывание, которое истинно тогда и только  тогда, когда истинно хотя бы  одно из этих высказываний.

     Дизъюнкцию  высказываний А и В мы обозначим символом А V В и будем читать: А или В. Определение дизъюнкции может быть записано в виде таблицы истинности:А В 

                                                        5 

Определение дизъюнкции двух высказываний естественным образом  распространяется на любое конечное число составляющих: дизъюнкция А1 V А2 V А3 V...V АN истинна тогда и только тогда, когда истинно хотя бы одно из высказываний А1, А2, А3, ..., АN (а следовательно, ложна, когда ложны все эти высказывания).

     Логическое  следование (импликация) от латинского implico - тесно связываю.

     В  наших рассуждениях, особенно в  математических доказательствах,  мы часто пользуемся сложными  высказываниями, образованными с  помощью слов "если..., то...". Здесь  высказывание, расположенное после  слова "если", называется основанием  или посылкой, а высказывание, расположенное  после слова "то", называется  следствием или заключением.

     Рассмотрим  пример: из арифметики. Вам должно  быть известно, что утверждение  "если каждое слагаемое делится  на 3, то и сумма делится на 3" истинно, т.е. из высказывания "каждое слагаемое делится  на 3" следует высказывание "сумма  делится на 3". Посмотрим, какие  наборы значений истинности посылки  и заключения возможны, когда  истинно все утверждение. Возьмем,  например, в качестве слагаемых  числа 6 и 9. В этом случае  истинны и посылка, и заключение, и все утверждение. Если же взять числа 4 и 5, то посылка будет ложной, а заключение истинным. Для чисел 4 и 7 и посылка и заключение ложны. (Если Вы сомневаетесь в истинности высказывания для последнего случая попробуйте произнести его в сослагательном наклонении: если бы числа 4 и 7 делились бы на 3, то и их сумма делилась бы на 3). Очевидно, что только один случай невозможен: мы не найдем таких двух слагаемых, чтобы каждое из них делилось на 3, а их сумма не делилась на 3, т.е. чтобы посылка была истинной, а заключение ложным. Из истины не может следовать ложь, иначе логика теряет смысл. Высказывание "Если А, то В" с логической точки зрения имеет тот же смысл, что и высказывание "неверно, что А истинно и В ложно".

                                                         6

 Это означает, что функцию импликации можно  заменить комбинацией двух функций 

(отрицания и  конъюнкции). Обычно, когда мы хотим  установить ложность высказывания "Если А, то В", мы стараемся показать, что возможен случай, когда А истинно, а В ложно (доказательство "от противного"). Обозначим импликацию символом => и запись "А => В" будем читать: "Из А следует В".

     Таким  образом, импликацией А => В называется высказывание, которое ложно тогда и только тогда, когда А истинно и В ложно.

     Запишем  это определение в виде таблицы истинности: 

 
 

Логическое тождество (эквиваленция).

     Интуитивно  можно догадаться, что высказывания  эквивалентны (равносильными), когда их значения истинности одинаковы. Например, эквивалентны высказывания: "железо тяжелое" и "пух легкий", так же как и высказывания: "железо легкое" и "пух тяжелый". Обозначим эквиваленцию символом <=> и запись "А <=> В" будем читать "А эквивалентно В", или "А равносильно В", или "А, если и только если В".

     Таким  образом, эквиваленцией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда оба эти высказывания А и В истинны или оба ложны.

     Отметим,  что высказывание типа "А, если  и только если В" можно заменить высказыванием "Если А, то В и, если В, то А" (обдумайте это на досуге и обратите внимание на символ <=>). Следовательно, функцию эквиваленции можно заменить комбинацией функций импликации и конъюнкции. Запишем таблицу истинности для эквиваленции: 

                                                    7

 

Приведем примеры  записи сложных высказываний с помощью  обозначения логических связок:

     "Быть  иль не быть - вот в чем вопрос." (В. Шекспир) А V ¬ A <=> В

     "Если  хочешь быть красивым, поступи  в гусары." (К. Прутков) А => В

3. Построение  таблиц истинности для логических  функций

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или  ложности простых. Эту функцию называют булевой функцией суждений f (a, b).

     Любая  логическая функция может быть  задана с помощью таблицы истинности, в левой части которой записывается  набор аргументов, а в правой  части - соответствующие значения  логической функции.

     При  построении таблицы истинности  необходимо учитывать порядок  выполнения логических операций. Операции в логическом выражении  выполняются слева направо с  учетом скобок в следующем  порядке:

     1. инверсия;

     2. конъюнкция;

     3. дизъюнкция;

     4. импликация и эквивалентность.

     Для  изменения указанного порядка  выполнения логических операций  используются круглые скобки.

     Предлагается  следующий алгоритм построения  таблицы истинности.

                                                 8

1. Определить  количество наборов входных переменных - всевозможных сочетаний значений  переменных, входящих в выражения,  по формуле: Q=2n , где n - количество входных переменных. Оно определяет количество строк таблицы.

     2. Внести в таблицу все наборы  входных переменных.

     3. Определить количество логических  операций и последовательность  их выполнения.

     4. Заполнить столбцы результатами  выполнения логических операций  в обозначенной последовательности.

 

Чтобы не повторить  или не пропустить ни одного возможного сочетания значений входных переменных, следует пользоваться одним из предлагаемых ниже способов заполнения таблицы.

     Способ 1. Каждый набор значений исходных  переменных есть код числа  в двоичной системе счисления,  причем количество разрядов числа  равно количеству входных переменных. Первый набор - число 0. Прибавляя  к текущему числу каждый раз  по 1, получаем очередной набор.  Последний набор - максимальное  значение двоичного числа для  данной длины кода.

     Например, для функции от трех переменных  последовательность наборов состоит  из чисел:

 

                                                  

                                                     9

Способ 2. Для  функции от трех переменных последовательность данных можно получить следующим  путем:

     а)  разделить колонку значений первой  переменной пополам и заполнить  верхнюю половину нулями, нижнюю  половину единицами;

     б)  в следующей колонке для второй  переменной половинку снова разделить  пополам и заполнить группами  нулей и единиц; аналогично заполнить  вторую половинку;

     в)  так делать до тех пор, пока  группы нулей и единиц не  будут состоять из одного символа.

     Способ 3. Воспользоваться известной таблицей  истинности для двух аргументов. Добавляя третий аргумент, сначала  записать первые 4 строки таблицы,  сочетая их со значением третьего  аргумента, равным 0, а затем еще  раз записать эти же 4 строки, но  теперь уже со значением третьего  аргумента, равным 1. В результате  в таблице для трех аргументов окажется 8 строк:

 
 

Например, построим таблицу истинности для логической функции: