Контрольная работа: Математическая логика
-
-
-
-
-
f 15
*
*
*
3.7 Принцип двойственности
Если в формуле алгебры логики F заменить знаки всех логических функций на знаки двойственных функций, то получится двойственная формула F * , реализующая функцию, двойственную той, которая реализуется формулой F . При этом, если формулы равны F 1 = F 2 , то верно равенство двойственных формул 
, которое называется двойственным предыдущему. Например, равенства, являющиеся двойственными друг другу:
и 
;
и 
;
и 
;
и 
;
и 
.
3.8 Полнота функций алгебры логики
Суперпозицией функций 
называется функция f , полученная с помощью подстановок этих функций друг в друга и переименования переменных, а формулой называется выражение, описывающее эту суперпозицию.
Например, суперпозицию функций f 1 , f 2 , f 3 можно задать формулой
.
Если f 1 обозначает дизъюнкцию, f 2 – конъюнкцию, а f 3 – сложение по mod 2, то последняя формула примет вид:
.
Если рассматривается произвольная система функций, то возникает вопрос: всякая ли логическая функция из этой системы представима формулой, содержащей символы только этой системы функций.
Система функций алгебры логики (ФАЛ) называется функционально полной , если любая функция алгебры логики может быть реализована формулой, содержащей лишь символы функций из этой системы ФАЛ, т.е. является суперпозицией функций из этой системы.
Следовательно, система функций должна быть функционально полной.
3.9 Теорема Поста – Яблонского (критерий функциональной полноты)