Язык логики высказываний
Логика высказываний (пропозициональная логика) – это раздел логики, изучающий способы построения и логическую структуру высказываний, отношения между ними и выводы, полученные с помощью логических операций конъюнкции, дизъюнкции, импликации, эквиваленции, отрицания и т.д. Часто в логике это обозначается КЛВ – классическая логика высказываний. Алфавит логики высказываний включает в себя четыре вида символов:
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 = 2n, где 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)