Теорема о тройке связок

1. Всякая истинностная функция может быть выражена формулой, содержащей только связки {, &, }.

Доказательство:

Рассмотрим два случая: (1) если f(х₁,х₂,…,х_n)0 – противоречие. Тогда очевидно, f(х₁,х₂,…,х_n)=, если f(х₁,х₂,…,х_n)1 – тавтология, то f(х₁,х₂,…,х_n)=, (2) если f(х₁,х₂,…,х_n)0 (и 1). Представим её в виде СДНФ или СКНФ. Тогда в полученной формуле имеются только связки из множества {, &, }.

Следствие 1: о парах связок

Для любой из следующих пар связок {Ø,&}, {Ø,Ú} и {Ø,®} и для любой функции алгебры логики можно построить формулу, реализующую эту функцию и содержащую связки только из заданной пары.

Доказательство:

Пусть для функции построена совершенная дизъюнктивная (или конъюнктивная) нормальная форма, т.е. формула, содержащая только связки {Ø,&,Ú}. Заметим, что выражение , является тождеством. Поэтому все выражения вида хÚу можно заменить эквивалентными и содержащими только связки {Ø,&}. Тем самым, полученная в результате проведенных преобразований формула, содержит только связки из заданной пары.

Для представления функции формулой со связками {Ø,Ú} аналогичным образом можно воспользоваться тождеством . И, выполнив замены всех подформул вида х&у на эквивалентную формулу , получить в результате формулу со связками из заданной пары.

Для перехода в формуле к последней паре связок {Ø,®} можно воспользоваться тождествами: и

Следствие 2: об уникальных связках

Любая истинностная функция может быть выражена формулой с использованием лишь одной связки стрелки Пирса – {¯}или штриха Шеффера – {½}.

Доказательство:

СКНФ(x½у)=

Нетрудно также проверить, что имеют место следующие тождества: и .

Тем самым, х & y = = (x¯x) ¯ (у¯у) и х  y = = (xx)  (уу). Последние тождества можно использовать для перехода в формуле от связок {Ø,&,Ú} к стрелке Пирса или к штриху Шеффера.

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

Рассмотрим применение следствий 1 и 2 на примере.

Запишем формулу ху с использованием только связок {Ø,&}: ху =. С использованием связок {Ø,Ú}: ху =. С использованием только {¯}: ху = ((х¯х) ¯ у) ¯ ((х¯х) ¯ у). И, наконец, с использованием только {}: ху = (x (уу)).