Реферат: Краткая методичка по логике

(pÞq)Þp = + p = p`q + p = p(`q + 1) = p 1 = p

Пример. Доказательство равносильности высказываний.

[ØpÞØqÙØr] = `p Þ`q`r = `p +`q`r = p +`q`r

{(ØpÞØq)Ù(ØpÞØr)} = (`pÞ`q)(`pÞ`r) = (p +`q)(p +`r) = p + p`r +`q p +`q`r = p(1 +`r +`q) +`q`r = p +`q`r

Т. о. […] = {…} т. е. являются равносильными два полученных ранее перевода высказывания «чай …».

Правилом отделения называется правило Dp, (p)Þ(q), q

Теорема о выводе в пропозициональной логике: высказывание p₀ является тавтологическим следствием из p₁ ,…,p_n тттк его можно получить из p₁ ,…, p_n с помощью правила отделения и нижеследующих пятнадцати беспосылочных правил:

DpÞqÞp

D (pÞpÞq)Þ(pÞq)

D (pÞq)Þ((qÞr)Þ(pÞr))

D pÙqÞp

D pÙqÞq

D (pÞq)Þ((pÞr)Þ(pÞqÙr))

D pÞpÚq

D qÞpÚq

D (pÞr)Þ((qÞr)Þ(pÚqÞr))

D (pÛq)Þ(pÞq)

D (pÛq)Þ(qÞp)

D (pÞq)Þ((qÞp)Þ(pÛq))

D (pÞq)Þ(ØqÞØp)

DpÞØØp

DØØpÞp

Другими словами, какое–либо высказывание p₀ является тавтологическим следствием из p₁ ,…,p_n тттк p₀ можно сделать членом последовательности высказываний, которая является индуктивной относительно этих шестнадцати правил и правил D p₁ ,…, Dp_n . Теорема не исключает случай n = 0.

Теорема о самодостаточной выразительности пропозициональной логики: для любой истинностной таблицы с n входными столбцами p₁ ,…,p_n и любого распределения истинностных значений в ее результирующем столбце можно составить соответствующее этому столбцу высказывание: справа от всех строк с истиной в результирующем столбце записываем конъюнкцию p₁ … p_n , затем над некоторыми p_k ставим черту отрицания так, чтобы все эти конъюнкции для всех строк были истинными, затем составляем дизъюнкцию из получившихся конъюнкций. Например:

p q r ?

0 0 0 0

0 0 1 0

0 1 0 1 p q`r

0 1 1 0