Перейти к содержимому
Topos Uranos
Русский

Обобщённые законы де Моргана и дистрибутивности

Краткое содержание

Законы де Моргана и дистрибутивности до сих пор формулировались для двух членов; нормальные же формы объединяют конъюнкции и дизъюнкции любого числа членов и требуют этих законов в такой общности. Этот урок определяет рекурсией конъюнкцию и дизъюнкцию списка формул (φ1,…,φn)(\varphi_1, \ldots, \varphi_n), которые записываются как ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i и ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i, с ассоциированием влево, и доказывает индукцией по числу членов лемму о значении (конъюнкция истинна тогда и только тогда, когда истинны все её члены; дизъюнкция же тогда и только тогда, когда истинен хотя бы один), обобщённую ассоциативность, которая позволяет перегруппировывать, независимость от порядка и от повторений, обобщённые законы де Моргана и обобщённую дистрибутивность в той форме, которую использует урок о нормальных формах: конъюнкция двух дизъюнкций, из nn и из mm членов, эквивалентна дизъюнкции nmnm конъюнкций, составленных из одного члена каждой, и двойственно. Задачи подсчитывают оценки, находят ошибку доказательства, которое выдаёт перегруппировку за определение, измеряют рост при распределении и получают из него тавтологию из 2n2^n членов.

Цели обучения

  1. Записывать конъюнкции и дизъюнкции из nn членов в обозначениях ⋀\bigwedge и ⋁\bigvee, развёртывать их в цепочки, ассоциированные влево, и вычислять их истинностное значение с помощью леммы о значении.
  2. Доказывать индукцией по числу членов обобщённую ассоциативность, независимость от порядка и от повторений и обобщённые законы де Моргана, различая на каждом шаге тождество цепочек и семантическую эквивалентность.
  3. Доказывать обобщённую дистрибутивность и двойственную к ней, организуя индукцию по двум индексам, и подсчитывать члены, которые даёт распределение.
  4. Находить ошибку доказательства по индукции, у которого база записана неверно или шаг скрывает перегруппировку, и исправлять его.

Законы для любого числа членов

Урок о семантическом следовании и эквивалентности установил законы эквивалентности для двух членов: среди них коммутативность и ассоциативность ∧\wedge и ∨\vee, законы де Моргана и обе дистрибутивности. Однако формула в дизъюнктивной нормальной форме есть дизъюнкция конъюнкций, каждая из которых имеет столько членов, сколько нужно, и приведение формулы к этой форме требует отрицать, перегруппировывать и распределять конъюнкции и дизъюнкции любой длины. Если это так, бинарных законов в их нынешнем виде недостаточно: их нужно распространить на nn членов, и сделать это сразу для всех nn.

При каждом фиксированном nn закон де Моргана для nn членов можно было бы проверить таблицей истинности из 2n2^n строк, записанной с nn переменными, а равномерная подстановка из предыдущего урока, применённая к эквиваленции обеих частей, распространила бы его на произвольные формулы. Но значений nn бесконечно много, и никакое количество таблиц их не исчерпывает. Отсюда следует, что утверждение «для всякого nn» есть не эквивалентность двух формул, а высказывание о бесконечном множестве эквивалентностей, сформулированное в метаязыке; его доказательство, как и доказательства урока об индукции по натуральным числам и по формулам, является внешним доказательством, и его инструмент есть индукция по числу членов. Обозначение ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i тоже принадлежит метаязыку: это не новый символ языка, а имя для цепочки кружков и дисков, точно так же, как и (φ∧ψ)(\varphi \wedge \psi).

Полезно сразу зафиксировать три отношения, которые нельзя смешивать. Равенство α=β\alpha = \beta говорит, что α\alpha и β\beta суть одна и та же цепочка; определения, которые записываются с помощью :=:=, вводят имена для цепочек, и то, что получается развёртыванием определения, равно, а не просто эквивалентно. Семантическая эквивалентность α≡β\alpha \eqsem \beta говорит, что v(α)=v(β)v(\alpha) = v(\beta) для всякой оценки vv. Доказуемая эквивалентность α⊣⊢β\alpha \dashv\vdash \beta из раздела о выводе говорит, что каждая из двух формул выводится из другой. Этот урок работает с первыми двумя; третья появляется лишь в одном замечании.

Что используется

Из урока о семантике логики высказываний берутся оценки, функции из переменных v1,v2,…v_1, v_2, \ldots в {0,1}\{0, 1\}, и их продолжение на все формулы, которое обозначается той же буквой vv; значения производных связок, вычисленные из официальных сокращений: v(¬φ)=1−v(φ)v(\neg\varphi) = 1 - v(\varphi), v((φ∧ψ))=v(φ) v(ψ)v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), так что конъюнкция принимает значение 11 тогда и только тогда, когда значение 11 принимают обе её компоненты, и v((φ∨ψ))=1v((\varphi \vee \psi)) = 1 тогда и только тогда, когда v(φ)=1v(\varphi) = 1 или v(ψ)=1v(\psi) = 1; лемма о совпадении (если две оценки совпадают на переменных формулы, они совпадают на формуле); и формулы ⊤\top и ⊥\bot, фиксированные тавтология и противоречие. Из урока о семантическом следовании и эквивалентности берутся рефлексивность, симметричность и транзитивность ≡\eqsem, теорема о семантической замене и каталог законов с их названиями: коммутативность, (φ∧ψ)≡(ψ∧φ)(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi) и (φ∨ψ)≡(ψ∨φ)(\varphi \vee \psi) \eqsem (\psi \vee \varphi); ассоциативность, (φ∧(ψ∧χ))≡((φ∧ψ)∧χ)(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi) и аналогичный закон для ∨\vee; законы де Моргана, ¬(φ∧ψ)≡(¬φ∨¬ψ)\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi) и ¬(φ∨ψ)≡(¬φ∧¬ψ)\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi); дистрибутивность, (φ∧(ψ∨χ))≡((φ∧ψ)∨(φ∧χ))(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi)) и (φ∨(ψ∧χ))≡((φ∨ψ)∧(φ∨χ))(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi)); двойное отрицание, ¬¬φ≡φ\neg\neg\varphi \eqsem \varphi; идемпотентность, (φ∨φ)≡φ(\varphi \vee \varphi) \eqsem \varphi; тождество, (φ∧⊤)≡φ(\varphi \wedge \top) \eqsem \varphi; и закон исключённого третьего, ⊨(φ∨¬φ)\models (\varphi \vee \neg\varphi). Законы верны для произвольных формул φ\varphi, ψ\psi, χ\chi, которые являются метапеременными.

На каждом шаге последующих доказательств часть формулы заменяется на эквивалентную. Теорема о семантической замене разрешает это для одного вхождения за раз; следующая лемма, которая является её частным случаем, даёт это сразу для частей отрицания, конъюнкции или дизъюнкции. Следует заметить, что это не синтаксическая тривиальность: ¬α\neg\alpha есть цепочка (α↓α)(\alpha \downarrow \alpha), в которой α\alpha встречается дважды, и (α∧β)(\alpha \wedge \beta) содержит, следовательно, восемь вхождений α\alpha и восемь вхождений β\beta.

ЛеммаСогласованность связок с эквивалентностью

Если α≡α′\alpha \eqsem \alpha' и β≡β′\beta \eqsem \beta', то ¬α≡¬α′\neg\alpha \eqsem \neg\alpha', (α∧β)≡(α′∧β′)(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta') и (α∨β)≡(α′∨β′)(\alpha \vee \beta) \eqsem (\alpha' \vee \beta').

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

  1. v(α)=v(α′),v(β)=v(β′)\dato{h}{v(\alpha) = v(\alpha'), \qquad v(\beta) = v(\beta')}

    Пусть vv есть произвольная оценка. По гипотезе α\alpha и α′\alpha' имеют одно и то же значение, а также β\beta и β′\beta'.

  2. v(¬α)=1−v(α)=1−v(α′)=v(¬α′),v((α∧β))=v(α) v(β)=v(α′) v(β′)=v((α′∧β′))v(\neg\alpha) = 1 - \resaltar{v(\alpha)} = 1 - \resaltar{v(\alpha')} = v(\neg\alpha'), \qquad v((\alpha \wedge \beta)) = \resaltar{v(\alpha)\,v(\beta)} = \resaltar{v(\alpha')\,v(\beta')} = v((\alpha' \wedge \beta'))

    Значение отрицания и значение конъюнкции зависят только от значений их компонент.

  3. v((α∨β))=1  ⇔  v(α)+v(β)≥1  ⇔  v(α′)+v(β′)≥1  ⇔  v((α′∨β′))=1v((\alpha \vee \beta)) = 1 \;\Leftrightarrow\; v(\alpha) + v(\beta) \geq 1 \;\Leftrightarrow\; v(\alpha') + v(\beta') \geq 1 \;\Leftrightarrow\; v((\alpha' \vee \beta')) = 1

    То же происходит с дизъюнкцией: она принимает значение 11 тогда и только тогда, когда какая-либо компонента принимает значение 11, а компоненты имеют одинаковые значения в обеих частях.

  4. ¬α≡¬α′,(α∧β)≡(α′∧β′),(α∨β)≡(α′∨β′)\neg\alpha \eqsem \neg\alpha', \qquad (\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta'), \qquad (\alpha \vee \beta) \eqsem (\alpha' \vee \beta')

    Поскольку оценка vv была произвольной, все три эквивалентности верны.