Конъюнкции и дизъюнкции над множеством переменных. нормальные формы

Определение.Конъюнкцией над множеством переменных Х=(х1,… ,хn) называется логическое произведение вида:

К= хi1a i1 . . . хisa is ,

где (хi1 , … , хis ) I Х, хika ik = xik либо`xik .

Конъюнкцию К можно представить как результат (s-1)применения двуместной функции логического умножения либо одной обобщенной функции , а также одноместной функции O . Аналогом функции по принципу действия (выделение 1 на крайней позиции вектора истинности) является функция Вебба¯. Поскольку правило x у=`x ¯ у справедливо для любого числа переменных, то любая конъюнкция Кможет быть представлена в виде: К=¯( хi1Oa i1, . . . , хisOa i s ), где ¯ ? обобщенная функция Вебба. Данное представление назовем представлением в базисном наборе(O, ¯). Отрицание`x может быть выражено при помощи функции Вебба следующими способами:`x = ¯(х, х) = ¯(х, 0) =¯(0, х ) (дублирующая подстановка (х, х) на практике реализуется замыканием входов элемента ¯ , а подстановка 0 ? заземлением соответствующего входа у функционального элемента (рис.1.5)). Поэтому любая конъюнкция Кможет быть полностью выражена при помощи элементов ¯ ( в базисном наборе(¯)). При этом общее число функциональных элементов в конъюнкции Кпри использовании обоих базисных наборов одинаково.

Конъюнкции и дизъюнкции над множеством переменных. нормальные формы

Рис.1.5

Определение. Дизъюнкцией над множеством переменных Х=(х1, … , хn)называется логическая сумма вида:

D= хi1a i1U. . . U хis a is,

где (хi1, … , хis ) I Х, хika ik = xik либо`xik .

Дизъюнкция D может быть реализована как при помощи (s-1)двуместной функции U, так и применением одной обобщенной функции U, а также одноместной функции O. Поскольку аналогом функции Uпо принципу действия (выделение 0 на крайней позиции вектора истинности) является функция штрих Шеффера |, то с учетом зависимости xU у =`x |` у, любая дизъюнкция D может быть представлена в виде:

D = | ( хi1Oa i1, . . . , хisOa is ),

где | ? обобщенная функция Шеффера. Данное представление назовем представлением в базисном наборе(O, | ).

Так как отрицание можно выразить через | :`x =| (х, х) = | (х,1) = |(1,х)(рис.1.6), то с использованием данных правил любая дизъюнкция D может быть полностью выражена при помощи элементов| ( в базисном наборе( | )). При этом у одной и той же дизъюнкции общее число функциональных символов при использовании обоих наборов также одинаково.

Конъюнкция, дизъюнкция, импликация, эквиваленция, отрицание. На примерах из жизни. Логика.


Читать еще…

Понравилась статья? Поделиться с друзьями: