Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

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

Установим ряд равносильностей, которые выражают одни логические связки через другие.

  • 1. А^В = ^ЛУ В.
  • 2. А = В = {А^В)к{В^А).
  • 3. А&В = ^(^AV~^В).
  • 4. АV В = —1(iyl&:—'В).

В пункте 3.3 мы уже доказали равносильность А—>В = ^А V В (табл. 3). Ясно, что равносильности 3 и 4 получаются из законов де Моргана, если взять отрицание формул, стоящих в левой и правой части, а затем воспользоваться законом двойного отрицания (см. пункт 3.3 формулы 9 и 8). Таким образом, в доказательстве нуждается только равносильность 2.

Для доказательства равносильности 2 рассмотрим два случая.

  • 1. Пусть Л и В принимают одинаковые значения. Тогда А = В = 1, и А—>В = 1, В—>А = 1. Отсюда (А—>В)&с(В—>А) = 1. Следовательно, в этом случае обе части равносильности имеют одинаковые истинностные значения.
  • 2. Пусть теперь А и В имеют различные логические значения. Тогда А = В — 0, и одна из импликаций А^В или В —> А принимает значение 0, следовательно —? В) (В —»А) — 0. Таким образом, и в этом случае обе части равносильности имеют одинаковые логические значения.

Таким образом, равносильность 1 показывает, что в любой формуле связку «—>» можно исключить, заменив ее связками «->» и «V». Из равносильности 2 с учетом предыдущего равенства следует, что связка «=» выражается через связки «&», «V» и «-<». Значит система связок {У, V, —i} является полной. А поскольку конъюнкция и дизъюнкция выражаются одна через другую с использованием отрицания (равносильности 3 и 4), то полными системами также являются системы связок {&, ->} и {V, —Отметим, что системы связок {У, ^} и {V, —минимальные, т. е. из них нельзя удалить ни одну из связок, не нарушая полноты.

Упражнение 3. Доказать равносильности:

Упражнение показывает полноту системы связок {—ц-Д.

Однако существуют полные системы связок, которые состоят из одной логической связки (операции), с помощью которой выражается любая из пяти, определенных ранее логических связок. Например, такой операцией является «штрих Шеффера». Она обозначается «|» и определяется следующей таблицей истинности:

А

В

АВ

0

0

1

0

1

1

1

0

1

1

1

0

Из табл. 5 легко следует, что АХВ = ^(АВ), а так как очевидно, что —= у1 |у1, то АХВ = (АВ)(АВ). Таким образом, из полноты системы связок {&, —<} следует, что любую логическую формулу можно заменить на равносильную ей формулу, содержащую только штрих Шеффера.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>