Логические функции от двух переменных

Логические операции

 

Будем считать, что уже имеется некоторый запас элементарных высказываний, относительно каждого из которых известно, истинно оно или ложно. В обычной речи мы часто используем слова, называемые логическими связками, — «не», «и», «или», «следует», «влечет», «эквивалентно», «равносильно», «тогда и только тогда, когда...» и т. п.

Примеры сложных высказываний:

1) {В автобусе можно доехать до школы и почитать журнал};

2) {Число 376 четно или двузначно};

3) {Неверно, что Солнце движется вокруг Земли};

4) {Если сумма цифр числа делится на 3, то число делится на 3}.

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

1. Логическая операция конъюнкция (лат. conjunctio — «связываю»):

• в естественном языке соответствует союзам и, а, но, хотя;

• обозначение: & или Ù;

• иное название: логическое умножение.

Конъюнкция — это логическая операция, ставящая в соответствие каждым двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.

Это определение распространяется и на случай п высказываний (п > 2, п —целое число). В соответствии с определением правила выполнения действий для операции конъюнкции можно представить в виде истинностной таблицы:

A	B	AÙB

Истина будет лишь в том случае, когда оба человека не лгут.

2. Логическая операция дизъюнкция (лат. disjunctio — «различаю»):

• в естественном языке соответствует союзу или;

• обозначение;

• иное название: логическое сложение.

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

Правила действия для операции дизъюнкции можно представить в виде истинностной таблицы:

A	B	AÚB

Выбирая между истиной и ложью, мы останавливаемся на истине.

В отличие от рассмотренной выше операции дизъюнкции можно рассмотреть строгую дизъюнкцию (двойное «или»), которой в естественном языке соответствует связка «либо..., либо...»). Суть этой операции ясна из приведенной ниже таблицы:

A	B	AÅB

Данная операция реализует сложение разряда двоичного числа без переноса в старший разряд.

3. Логическая операция импликация (лат. implicatio — «тесно связываю»):

• в естественном языке соответствует обороту если..., то...;

• обозначение: =>;

• иное название: логическое следование.

Импликация — это логическая операция, ставящая в соответствие каждым двум элементарным высказываниям новое высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно. Таблица истинности импликации:

A	B	AÞB

Из лжи может следовать что угодно, даже истина, но из истины не может следовать ложь.

4. Логическая операция э квиваленция (лат. aequivalens — «равноценное»):

• в естественном языке соответствует оборотам речи тогда и только тогда, в том и только в том случае;

• обозначение:Û;

• иное название: равнозначность.

Эквиваленция — это логическая операция, ставящая в соответствие каждым двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны. Эквивалентны ли высказывания, то есть одинаковы ли значения высказываний?

Таблица истинности эквиваленции:

A	B	AÛB

 

5. Логическая операция инверсия (лат. inversio — «переворачиваю»):

• в естественном языке соответствует словам неверно, что... и частице не;

• обозначение: ;

• иное название: отрицание.

Отрицание — это логическая операция, которая каждому данному высказыванию ставит в соответствие новое высказывание, которое истинно, если данное высказывание ложно, и ложно, если данное высказывание истинно.

Таблица истинности инверсии:

 

A

 

Логические операции имеют следующий приоритет: действия в скобках, отрицание, Ù, v, =>,<=>.

 

Таблицы истинности

 

Логические функции могут быть заданы табличным способом или аналитически — в виде соответствующих формул.

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

Поэтому любое сложное высказывание можно рассматривать как некоторую логическую функцию F(X 1, Х 2 ,..., Хn).

Определим количество различных логических функций с заданным числом переменных п. Логическая функция на каждом наборе переменных принимает значение 0 или 1.

Следовательно, отличающихся друг от друга функций может быть ровно столько, сколько существует различных комбинаций из m = 2 ⁿ нулей и единиц.

Таких комбинаций 2 ⁿ, и они представляют собой последовательность n -разрядных двоичных чисел от 0 до 2 ⁿ – 1.

Логические функции от двух переменных

Пусть п = 2. Существует 16 различных логических функций от двух переменных. Рассмотрим их подробно:

 

Аргу-менты

Функции

X1

X2

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

F₁ — константа 0.

F₂ — конъюнкция.

F₃ — отрицательные импликации X₁ и X₂.

F₄ — функция, повторяющая переменная X₁.

F₅ — отрицание импликации X₂ и X₁.

F₆ — переменная X₂.

F₇ — строгая дизъюнкция или отрицание эквивалентности
(неравнозначность) переменных X₁ и X₂. Значение этой функции получается поразрядным сложением двоичных переменных X₁ и X₂ по модулю 2, то есть без учета переноса в старший разряд.

F₈ — дизъюнкция.

F₉ — отрицание дизъюнкции (функция ИЛИ-НЕ); эта функция называется также функцией Пирса («стрелка» Пирс).

F₁₀ — эквивалентность.

F₁₁ — отрицание переменной X₂.

F₁₂ — импликация X₁ и X₂.

F₁₃ — отрицание X₁.

F₁₄ —импликация X₁ и X₂.

F₁₅ — отрицание конъюнкции (функция И-НЕ); эта функция называется также функцией Шеффера («штрих» Шеффера).

F₁₆ — константа 1.

С увеличением числа аргументов количество логических функций резко возрастает. Так, при п = 3 их будет уже 256. Но изучать их все нет никакой необходимости. Дело в том, что функция любого количества переменных может быть выражена через функции только двух переменных. Делается это с помощью приема суперпозиции, состоящего в том, что, во-первых, на место переменных подставляются функции, во-вторых, переменные меняются местами.

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

Вот несколько примеров функционально полных наборов:

1) F2 и F11; 2) F13 и F8; 3) F9 и F15.

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

Введенные пять логических операций дают возможность из простых высказываний строить сложные. Всякое сложное высказывание принимает значение 1 или 0 в зависимости от значения простых высказываний, из которых оно построено.

Таблицу, показывающую, какие значения принимает сложное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности сложного высказывания. Сложные высказывания часто называют формулами логики высказываний. Для любой формулы алгебры логики достаточно просто построить таблицу истинности.

 

Поделиться:

Воспользуйтесь поиском по сайту: