Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 11

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 101 >> Следующая


Примеры.

р : Наполеон умер на острове Св. Елены. 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 и т. п.
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed