195
правок
Изменения
м
→Метод Квайна
*Операция попарного неполного склеивания:
:<tex>A x \lor A \neg x = A x \lor A \neg x \lor A</tex>
*Операция элементарного поглощения:
:<tex>A \tilde x \lor A = A </tex>
:(где <tex>A</tex> {{---}} некоторая элементарная конъюнкция, то есть конъюнкт, в который каждая из переменных входит не более одного раза)
'''Например:'''
Пусть <tex>A = y\neg z\neg w</tex>, тогда:
*Операция попарного неполного склеивания:
:<tex>y\neg z\neg w x \lor y\neg z\neg w \neg x = y\neg z\neg w x \lor y\neg z\neg w \neg x \lor y\neg z\neg w</tex>
*Операция элементарного поглощения:
:<tex>y\neg z\neg w \tilde x \lor y\neg z\neg w = y\neg z\neg w</tex>
Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ пока это может быть осуществимо.
====Описание алгоритма====
