Упражнение 2.1.8

Построить логическую функцию по формуле

.

Какие из переменных являются существенными?

Построив истинностную таблицу формулы S, получим функцию, соответствующую данной формуле (табл. 2.1.10).

При различных значениях истинности и ложности переменной х₃ и фиксированных значениях переменных х₁ и х₂ значения функции одинаковы. Следовательно, х₃ – фиктивная переменная. Существенными являются переменные х₁ и х₂. Сравнивая вторую и четвертые строки табл. 2.1.10, обнаруживаем, что при одинаковых значениях истинности переменных х₁=1 х₃=0 и разных значениях х₂ (1,0), значения функции разные, т.е. f(1,1,0) ≠ f(1,0,0), следовательно, х₂ – существенная переменная. Сравнивая четвертую и восьмую строки таблицы, получим f(1,0,0) не равно f(0,0,0), т.е. х₁ – существенная переменная.

Таблица 2.1.10

х1	х2	х3					f

В том, что х₃ – фиктивная переменная, можно убедиться преобразованием формулы S.

Таблица 2.1.11

Этой формуле соответствует функция g, получаемая из f удалением фиктивной переменной х₃ (табл. 2.1.11).

Выпишем все функции от двух переменных. Очевидно их будет =16 (табл. 2.1.12).

Таблица 2.1.12

Очевидно, введенные ранее связки Ù, Ú, ®, « есть соответственно функции f₈, f₁₄, f₁₁, f₉. В качестве связок используются и другие функции, в частности

F₇ – штрих Шеффера х₁½х₂,

F₁ – знак Лукашевича х₁¯х₂,

F₆ – разделительная дизъюнкция , соответствующая разделительному союзу «или».

Полные системы связок

Система связок логики высказываний называется полной, если всякая формула логики высказываний равносильна некоторой формуле, содержащей лишь связки этой системы.

Используя формулы, равносильные импликации и двойной импликации, получим, что дизъюнкция, конъюнкция, отрицание образуют полную систему связок. Используя закон де Моргана, приходим к тому, что (Ú-), (Ù-) – полные системы связок.

В самом деле из трех связок Ú, Ù, ^¾ можно исключить дизъюнкцию: или конъюнкцию: .

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

Набор таких связок, как отрицание и двойная импликация – неполон, так же как и {Ú, ®}{Ù, Ú, ®, «}.