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

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

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

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

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

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

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

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

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

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 в зависимости от значения простых высказываний, из которых оно построено.

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