ЛМвИИ (1086253), страница 5
Текст из файла (страница 5)
Запись А≡В будет означать, что высказывания А и Вравносильны.Основные равносильности исчисления высказываний:1. Коммутативный законAvB≡BvA,A^B≡B^A.2. Ассоциативный законAv (ВvC)≡(Av В) v C,А^ (В ^ C)≡(А ^ В)^С.3. Дистрибутивный законAv(B^C) ≡ (AvB )^(Av C),A^(BvC) ≡ (А^ B)v(A^C).4. Закон Де Моргана¬(AvB) ≡ ¬A^¬B,¬(A^B) ≡ ¬Av¬B5. Закон идемпотентностиAvA≡A,A^A≡A.6.
Закон поглощенияАv(А ^ B)≡A, A^(AvB) ≡ A, Av(¬A^ B)≡AvB.7. Закон склеивания7'. Закон неполного склеивания(A^B)v(A^¬B)≡A(A^B)v(A^¬B)≡Av(A^B) v (А^¬В)8. Закон исключенного третьегоAv¬A=lи закон противоречияА^¬А=09. Закон двойного отрицания ¬¬A≡A или в общем случа嬬...¬ A ≡{ A , если n−чётное }¬ A , если n−нечётноеn раз10.11.12.13.14.15.16.17.18.Av0≡A,А^0≡0Av1 ≡ 1,A^1 ≡ A¬0≡1,¬1≡0A→B ≡ ¬AvBА↔В ≡ (А→В)^(В→А) ≡ (A^B)v(¬A^¬B) ≡ (¬AvB)^(Av¬B)А⊕В ≡ (A^¬B)v(¬A^B)A|B ≡ ¬(A^B) ≡ ¬Av¬BA↓B ≡ ¬(AvB) ≡ ¬A^¬BКонтрапозиция А→В ≡ ¬В→¬А.Необходимо сделать некоторые- дополнения о импликации. Эта связка отражаетструктуру рассуждений. Первый операнд называется посылкой (или антецедентом), а второй заключением (или консеквентом). Из таблицы истинности следует, что при истинностипосылки заключение истинно.
Однако, и при ложной посылке заключение может оказатьсяистинным. Эта единственная связка, обладающая свойством:• если посылка истинна, истинность импликации совпадает с истинностью заключения;• значение истинности зависит от двух операндов;• импликация некоммутативна.Теперь покажем примеры выполнимых, невыполнимых и общезначимых формул:высказывание а выполнимо, отрицание высказывания также выполнимо; (avb) и (а^b) выполнимые формулы: они истинны, в частности, при истинности а и b. Формула (a^¬a)невыполнима. Общезначимые формулы: (av¬a), (a→а), ¬¬а.Покажем, как использовать таблицы истинности для доказательства общезначимостиформулы(a → (b → c)) ↔ ((a ^ b) → c)Таблица истинности будет содержать восемь строк - интерпретаций (n=3, 23=8).Обозначим левую часть этой формулы буквой А, а правую - В, т.е. имеем А↔В.
Таблицаистинности примет следующий вид:Таблица 1.2abcb→ca→(b→c)a^b(a^b)→cA↔BИИИИИИИИИИЛЛЛИЛИИЛИИИЛИИИЛЛИИЛИИЛИИИИЛИИЛИЛЛИЛИИЛЛИИИЛИИЛЛЛИИЛИИ1.4. Формы представления высказываний.Одно и то же сложное высказывание может быть представлено в различных формах.Элементарной дизъюнкцией называется выражение A1v...vAi ...vAn , где каждое Ai(i=1..n) является либо элементарным высказыванием, либо отрицанием элементарноговысказывания и Ai≠Aj при i≠j. Пустой дизъюнкт - единственный невыполнимый дизъюнкт. Егообычно обозначают или Л.Элементарной конъюнкцией называется выражение B1^B2^...^Bm , где каждое Вi (i=1..m)является либо элементарным высказыванием, либо отрицанием элементарного высказывания.Исчисление высказываний занимается только теми логическими соотношениями,которые возникают из факта построения одних высказываний из других (называемыхэлементарными формулами, или атомами), которые уже не анализируются.В классическом исчислении высказываний принято, что всякое неанализируемоевысказывание (атом) истинно или ложно, но не то и другое вместе.1.2.3.Примеры:¬xvyv¬zx^¬y^¬z¬x4.x^y v z5.6.¬(xvy) v zx^¬(у^z)- элементарная дизъюнкция- элементарная конъюнкция- можно считать частным случаем как элементарной конъюнкции, таки элементарной дизъюнкции;- не является ни элементарной конъюнкцией, ни элементарной`конъюнкцией;- не является элементарной дизъюнкцией;- не является элементарной конъюнкцией.Дизъюнктивной нормальной формой (ДНФ) данного высказывания называетсяравносильное ему высказывание вида K1v...vKi...vKS, где Ki (i=1..s) - элементарная конъюнкция.Конъюнктивной нормальной формой (КНФ) данного высказывания называетсяравносильное ему высказывание вида D1^...^Di...^DT, где Di (i=1..t) - элементарная дизъюнкция.Алгоритм приведения формулы к нормализованной конъюнктивной форме достаточнопрост:• Сначала исключаются из формул в соответствии с приведенными вышеравносильностями связки →, ↔.• Необходимое число раз применяются правила Де Моргана.• Применяется правило дистрибутивности.В процессе приведения исходной формулы необходимо упростить полученную напромежуточном этапе формулу.
При этом надо помнить, что дизъюнкты, содержащиепротивоположные литеры (т.е. высказывание и его отрицание), общезначимы и могут бытьопущены. Кроме того, можно опустить повторения одного и того же высказывания в пределаходного дизъюнкта.На простом примере покажем применение этих правил для приведения формулы кКНФ.Понятие дизъюнкта используется в логическом программировании и, в частности, вязыке Пролог.Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая ДНФ,в которой каждая элементарная конъюнкция (называемая также конституентой единицы)содержит все элементарные высказывания либо их отрицания по одному разу. Конституентыединицы в СДНФ не повторяются.Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ,в которой элементарная дизъюнкция (называемая также конституентой нуля) содержит всеэлементарные высказывания либо их отрицания по одному разу.
Конституенты нуля в СКНФ неповторяются.Каждое высказывание, кроме тавтологии и противоречия, имеет единственную СДНФ иединственную СКНФ.Тавтология не имеет СКНФ. а противоречие — СДНФ.1.2.3.4.5.6.7.8.Примеры:(x^y)v(x^z)vy - ДНФ;(xv¬y)^(¬xv¬z)^x - КНФ(¬x^y^¬z)v(x^¬y^z)v(x^y^z)v(¬x^¬y^¬z) - СДНФ(x v y v z) ^ (¬x v y v ¬z) ^ (¬x v ¬y v z) - СКНФ.¬xvy - можно рассматривать как ДНФ и как КНФ.(¬x ^ y ^ z) v (x ^ ¬y ^ z) - является СДНФ.(x v ¬y v ¬z) ^ (w v ¬x v ¬z) - не является СКНФ.(x^y^¬z)v(x^y^z)v(x^y^¬z) - не является СДНФ.При переходе от ДНФ к СДНФ используются следующие равносильности:A^1 ≡ A;Bv¬B≡1;A≡A^(Bv¬B)≡(A^B)v(A^¬B)Пример:Привести к КНФ формулу (x→(y→z))→((x^q)→z).Исключим импликации:¬(x→(y→z)v((x^q)→z) = ¬(¬xv(¬yvz))v(¬(x^q)vz).Внесем внешние отрицания в скобки, используя закон Де Моргана:(¬¬x^¬(¬yvz))v(¬(x^q)vz) = (x^(¬¬y^¬z))v(¬xv¬qvz) = (x^(y^¬z))v(¬xv¬qvz).Теперь применим дистрибутивный закон и одновременно упростим получаемыевыражения, помня замечание об общезначимости дизъюнкта, содержащего противоречие:(xv(¬xv¬qvz))^((y^¬z)v(¬xv¬qvz)) = (xv¬xv¬qvz)^(yv¬xv¬qvz)^(¬zv¬xv¬qvz).Первая и третья скобки (дизъюнкты) общезначимы, поэтому И^(yv¬xv¬qvz)^И =¬xvyv¬qvz.
Таким образом, полученная конъюнктивная нормальная форма содержит одиндизъюнкт. Эта формула ложна при истинности х, ложности у истинности q и ложности z.Пример:xv(¬x^y)v(¬x^¬y^z) = x^(yv¬y)^(zv¬z)v(¬x^y)^(zv¬z)v(¬x^¬y^z) =(x^y^z)v(x^y^¬z)v(x^¬y^z)v(x^¬y^¬z)v(¬x^y^z)v(¬x^y^¬z)v(¬x^¬y^z).При переходе от КНФ к СКНФ используются следующие равносильности:Av0 ≡ A;B^¬B ≡ 0;A ≡ Av(B^¬B) ≡ (AvB)^(Av¬B).Пример:x^(¬xvy)^(¬xv¬yv¬z) = [xv(y^¬y)v(z^¬z)]^[¬xv¬yv(z^¬z)]^(¬xv¬yvz) =(xvxvz)^(xvyv¬z)^(xv¬yvz)^(xv¬yv¬z)^(¬xvyvz)^(¬xvyv¬z)^(¬xv¬yvz).При переходе от СДНФ к СКНФ вначале необходимо получить отрицание исходноговысказывания за счет выписывания через дизъюнкцию недостающих (до полного перечня)конституент единицы, а затем взять отрицание этого высказывания и выполнить преобразованияпо закону Де Моргана.Пример:f = (x^y^z)v(x^y^¬z)v(x^¬y^z)v(x^¬y^¬z)v(¬x^y^z);¬f = (¬x^¬y^¬z)v(¬x^¬y^z)v(¬x^y^¬z);¬¬f = ¬[(¬x^¬y^¬z)v(¬x^¬y^z)v(¬x^y^¬z)] = (xvyvz)^(xvyv¬z)^(xv¬yvz).При переходе от СДНФ к СКНФ вначале необходимо получить отрицание исходноговысказывания за счет выписывания через дизъюнкцию недостающих (до полного перечня)конституент единицы, а затем взять отрицание этого высказывания и выполнить преобразованияпо закону Де Моргана.Пример:f = (x^y^z)v(x^¬y^z)v(x^y^¬z)v(x^¬y^¬z)v(¬x^y^z);¬f = (¬x^¬y^¬z)v(¬x^¬y^z)v(¬x^y^¬z);¬¬f = ¬[(¬x^¬y^¬z)v(¬x^¬y^z)v(¬x^y^¬z)] = (xvyvz)^(xvyv¬z)^(xv¬yvz).При переходе от СКНФ к СДНФ вначале необходимо получить отрицание исходноговысказывания за счет выписывания через конъюнкцию недостающих (до полного перечня)конституент нуля, а затем взять отрицание этого высказывания и выполнить преобразования позакону Де Моргана.Пример:f = (xvyvz)^(xvyv¬z)^(xv¬yvz);¬f = (¬xv¬yv¬z)^(¬xvyv¬z)^(¬xv¬yvz)^(¬xvyvz)^(xv¬yv¬z);¬¬f = f = ¬[(¬xv¬yv¬z)^(¬xvyv¬z)^(¬xv¬yvz)^(¬xvyvz)^(xv¬yv¬z)] =(x^y^y^z)v(x^¬y^z)v(x^y^¬z)v(x^¬y^¬z)v(¬x^y^z).1.4.1.
Минимизация сложных высказываний с помощьюметода Квайна.Существуют различные методы минимизации сложных высказываний. Рассмотримодин из них, удобный для алгоритмизации, а следовательно, для переноса процессаминимизации на ЭВМ - метод Квайна. Этот метод использует следующие равносильности:• неполное склеивание (А^В)v(А^¬В) ≡ (А^В)v(А^¬В)vА;• поглощение AvA^B ≡ A.1.2.3.Минимизация выполняется в три этапа:Высказывание из произвольной формы переводится в СДНФ.Исходя из СДНФ, получают сокращенную дизъюнктивную форму (СкДНФ).На основе СДНФ и СкДНФ строится импликантная матрица, с помощью которойполучается минимальная дизъюнктивная нормальная форма (МДНФ).Заметим, что данный метод (как и большинство других) находит минимальную средидизъюнктивных нормальных форму для данного высказывания (т.е. требование нормальностиформы является серьезным ограничением).Первый этап минимизации был рассмотрен ранее, когда обсуждался переход от ДНФ кСДНФ.На втором этапе минимизации СДНФ выполняют все возможные операциипоглощения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
