Язык логики высказываний

Логика высказываний (пропозициональная логика) – это раздел логики, изучающий способы построения и логическую структуру высказываний, отношения между ними и выводы, полученные с помощью логических операций конъюнкции, дизъюнкции, импликации, эквиваленции, отрицания и т.д. Часто в логике это обозначается КЛВ – классическая логика высказываний. Алфавит логики высказываний включает в себя четыре вида символов:

1) пропозициональные переменные – p, q, r, s,...

2) пропозициональные связки – Ø, &, Ú, Ú, É, º

3) скобки – (…)

4) запятая -,

Пропозициональные переменные замещают собой простые высказывания. Например, высказывание «идет снег» можно обозначить символом p, высказывание «метет метель» – символом q, и т.д. Пропозициональные связки предназначены для того, чтобы объединять простые высказывания в более сложные. К ним относятся:

Ø – отрицание («не»; «неверно, что», «неправда, что» и т.п.)

& – конъюнкция («и», «а», «но», «хотя», и т.п.)

Ú – дизъюнкция («или», «по крайней мере одно из двух» и т.п.)

Ú – строгая дизъюнкция («либо-либо», «только одно из двух» и т.п.)

É – импликация («если, то», «значит», «вытекает» и т.п.)

º – эквиваленция («если и только если», «равнозначно» и т.п.)

Формулами в языке КЛВ называютзначимые выражения. Пропозициональные переменные сами по себе уже являются (атомарными) формулами. Более сложные формулы получаются из атомарных с использованием связок.

Определение формулы. (1) Пропозициональные переменные являются формулами. (2) Если А и В – формулы, то ØА, А&В, АÚВ, А Ú В, АÉВ, АºВ – тоже формулы. (3) Ничто другое не является формулой.

Упражнение 1. Расставьте пропущенные скобки в следующих формулах:

а) p Ú Ø q & r É s & q Ú Ø p º Øs É q Ú r

б) p & q º r & s Ú q Ú Ø p É Øs Ú q & r

Переводить высказывания с обычного языка на естественный не трудно. Пусть, например, р означает «Иван-царевич любит Марью», q – «Марья любит Ивана-царевича», r – «Марья красивая», s – «Иван-царевич храбрый». Тогда переводом следующих высказываний будут формулы:

– «Иван-царевич храбрый и любит Марью» s & p

– «Неверно, что Марья некрасивая

или Иван-царевич ее не любит» Ø(Ør Ú Øp)

– «Если Марья красива, а Иван-царевич храбр,

то они любят друг друга» (r&s) É (p&q)

Семантика языка КЛВ основана на двух принципах:

1) Принцип бивалентности. Каждая пропозициональная переменная, замещающая собой простое предложение, может быть либо истинной, либо ложной. Истинность будем обозначать как 1, ложность – как 0.

2) Принцип композициональности. Истинностное значение сложной формулы есть функция от истинностных значений входящих в нее переменных.

Таким образом, каждая пропозициональная связка трактуется как истинностно-истинностная функция. Для наглядности воспользуемся таблицей истинности:

p	q	Øp	p&q	pÚq	p Ú q	pÉq	pºq

Рассмотрим на примере, как строится таблица истинности для произвольной формулы. Пусть нам дано высказывание: «Если Иван-царевич и Марья любят друга, то неверно, что по крайней мере один из них не любит другого». Его переводом на язык КЛВ будет формула: (p&q) É Ø(ØpÚØq).

Алгоритм построения таблицы истинности:

1) Определить число строк (оно вычисляется по формуле k = 2ⁿ, где k – количество строк, а n – число различных пропозициональных переменных, входящих в формулу).

2) Задать все комбинации совместной истинности/ложности пропозициональных переменных[1].

3) Вычислить (построчно) значение каждой подформулы и формулы в целом (используя данное выше табличное определение пропозициональных связок).

p	q	Øp	Øq	p&q	ØpÚØq	Ø(ØpÚØq)	(p&q) É Ø(ØpÚØq)

В данной таблице всего четыре строки, поскольку формула содержит лишь две переменные – p и q. Первые два столбца задают все возможные комбинации совместной истинности и ложности этих переменных. Следующие пять столбцов показывают, каким будет значение каждой подформулы в той или иной строчке. Последний (результирующий) столбец показывает значение всей формулы в целом.

В зависимости от того, каким является результирующий столбец таблицы, выделяют три вида формул: тождественно-истинные, тождественно-ложные и логически случайные.

Тождественно-истинной (общезначимой) называется формула, принимающая значение «1» во всех строках таблицы.

Тождественно-ложной (невыполнимой) называется формула, принимающая значение «0» во всех строках таблицы.

Логически случайной (собственно выполнимой) называется формула, принимающая в некоторых строках таблицы значение «1», а в некоторых – «0».

В приведенном примере формула является тождественно-истинной. Она истинна всегда, независимо от того, истинны или ложны входящие в нее пропозициональные переменные. Другими словами, данная формула выражает собой логический закон.

Упражнение 2. установите табличным способом, к каким видам относятся следующие формулы:

а) Ø(p & q) º (Øp & Øq)

б) (p É q) É (Øq É Øp)

в) (p º q) & (p Ú q)