Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Примеры.
р : Наполеон умер на острове Св. Елены. q : Верцингеторикс носил усы.
р ZD q принимает значение q. р : 2X2 = 5. q : 12 — простое число.
р гэ q принимает значение 1. р : Луна состоит из овечьего сыра. q : 17 — простое число.
р zd q принимает значение 1. р : 17 — простое число. q : 16 —простое число.
р гэ q принимает значение 0. Здесь нет никакого парадокса; вскоре мы в этом убедимся.
Правило вывода (modus ponens). Если мы знаем (откуда —нас сейчас не касается!), что р имеет значение 1 и PZDii имеет значение 1, то мы можем сделать вывод, что и q имеет значение 1.
2.1.6. Логическая эквивалентность
Из двух высказываний (или пропозициональных переменных) р и q можно образовать высказывание р гз q, определяемое таблицейГ л //. Общие сведения о формальных системах
33
P <7 р и q
0 0 1
0 1 0
1 0 0
1 1 I
Здесь фактически представлено высказывание «р эквивалентно q», или, что то же самое, «р имеет то же логическое значение, что и q».
Как и в случае импликации, при образовании логической эквивалентности реальное содержание соединяемых высказываний совершенно не принимается во внимание.
2.1.7. Классификация логических выражений
Пусть у нас имеется конечное или бесконечное число пропозициональных переменных p,q, ... ; будем образовывать из них выражения последовательным применением логических операций Д, V, І, =5,
Примеры.
(р V р) Л q, (pzdq)\J(qzd р).
1) Существуют выражения, которые принимают значение 1, каковы бы ни были значения входящих в них переменных.
Примеры.
р V-Ip, р=>р.
В силу якобы парадоксального характера нашей импликации таким является и выражение
р ZD (q ZD р) ... . NB!
Такие выражения называются тождественно истинными, или тавтологиями.
2) Существуют выражения, которые принимают значение 0, каковы бы ни были значения входящих в них переменных.
Примеры.
р Alp, (р V 1Р) => (р Л 1 р)-
Такие выражения называются тождественно ложными, или противоречивыми.
3) Существуют, наконец, выражения, которые принимают то значение 1, то значение 0 в зависимости от того, каковы значения входящих в них переменных.34
Часть /. Предварительные сведения из логики и алгебры
Пример. (р => ?) V (р Л q).
В самом деле, обозначив это высказывание через г, мы получим
P 0 г
0 0 1
0 1 1
1 0 0
1 1 1
Поиск тавтологий представляет особый интерес, поскольку в логике тавтологии играют ту же роль, что в алгебре — тождества.
Пример. Выражение
(~1 Ч => ~1 Р) => (Р => Я)
является тавтологией (что нетрудно доказать, построив таблицу истинности). Эта тавтология лежит в основе правила контрапо-зиции.
Тавтологическая эквивалентность. Мы будем писать
г = s,
желая выразить тот факт, что высказывание
t = s
является тавтологией. Примеры.
(р V <7) V m = р V (q V m), (р Л q) Л m = р Л (q Л пг),
р =D q = 1 р V q), ГС!
P = <J = (Р=>Ф A (q=>p)-
Отношение = (мы будем называть его тавтологической эквивалентностью) означает, что при любых условиях выражения, стоящие слева и справа от символа =, принимают одно и то же логическое значение. Это отношение является отношением эквивалентности (иначе говоря, оно рефлексивно, симметрично и транзитивно).
Константа истина тавтологически эквивалентна любой тавтологии. Например:
PV-Ip = истина.
Константа ложь тавтологически эквивалентна любому противоречивому выражению. Например:
P Л "1P = ложь.Г л //. Общие сведения о формальных системах 35
2.1.8. Правила де Моргана
Легко убедиться в том, что выражения
~1(р V?) = IP A -Iq, I(PAq) = -^P V~lq
являются тавтологическими эквивалентностями. Эти эквивалентности называются правилами де Моргана.
Для большей компактности записи будем писать р вместо ~1р,
Для любых переменных или выражений г, s, t имеем
1°. г V г = г; г А г = г: идемпотентность;
2°. г V S = S V г; г As = S Ar: коммутативность; .
3°. г V (s V t) = (г V s) V t; г A (s Д t) = (г Д s) Д t: ассоциативность;
4°. rV(rAs) = r = rA(rVs);
5°. г V (s Д t) = (г V s) А (г V Л 1
д / V/ a / A \w/ а л f: дистрибутивность; г Л (s V = (г Л s) V (г А О I
6°. г V г = истина; г Ar = ложь;
7°. г V S = г Л S )
--_ двойственность (правила де Моргана);
г A S = г V S '
8°. (г) = г: инволютивность отрицания.
Соотношения I0—7° показывают, что исчисление высказываний снабжает множество логических выражений структурой булевой алгебры — это следует из самого определения булевой алгебры. (Точнее, мы имеем здесь в виду выражения, полученные из элементов счетного множества переменных р, q ... путем применения унарной операции —I и бинарных операций Vha произвольное число раз, причем тавтологически эквивалентные выражения считаются равными.)
2.1.9. Теоретико-множественная интерпретация исчисления высказываний
Возьмем семейство множеств Р, Q ... и будем интерпретировать пропозициональные переменные р, q, ... как выражения вида
хєР, xeQ, ... с одним и тем же х.
Тогда р Aq интерпретируется как xePDQ, pVq — как X єР U Q и т. п.