Реферат: Алгебра висловлень
f (1,1,...,1,1)
Серед формул алгебри висловлень особливе місце займають ті формули A (p 1 ,p 2 ,...,pn ), які на всіх наборах (a 1 ,a 2 ,...,an ) значень своїх змінних набувають значення 1.
Формула алгебри висловлень A (p 1 ,p 2 ,...,pn ) називається тавтологією тоді і тільки тоді, коли їй відповідає функція істинності, яка тотожно дорівнює 1.
Тавтології ще називають тотожно істинними формулами, або законами алгебри висловлень. Аналогом тавтології у природній мові є поняття істинного твердження.
Наведемо приклади деяких важливих тавтологій:
(p Ú(Øp )) (закон виключення третього ),
(Ø(p Ù(Øp ))) (закон виключення суперечності ),
(p ®p ) (закон тотожності ).
Довести, що ці формули є тавтологіями можна за допомогою відповідних таблиць істинності. Той факт, що формула A алгебри висловлень є тавтологією позначають так |=A . Символ |=, як і A належать метамові.
Формула алгебри висловлень A (p 1 ,p 2 ,...,pn ), яка набуває значення 0 на всіх наборах (a 1 ,a 2 ,...,an ) значень своїх пропозиційних змінних, називається суперечністю , або тотожно хибною формулою.
Формулу, яка не є ні тавтологією, ні суперечністю, називають нейтральною .
Множина всіх формул алгебри висловлень розбивається на тавтології, суперечності та нейтральні формули.
Формула, яка не є суперечністю, називається виконуваною .
Наведемо ряд тверджень, справедливість яких очевидна.
1. Заперечення тавтології є суперечністю і навпаки.
2. Кожна тавтологія є виконуваною формулою (навпаки, взагалі кажучи, ні).
3. Кожна нейтральна формула є виконуваною, але не навпаки.
4. Заперечення виконуваної формули може бути, як виконуваною формулою, так і невиконуваною формулою.
Дві формули A і B алгебри висловлень називаються рівносильними , якщо їм відповідає та сама функція істинності. Рівносильність формул A і B позначають за допомогою знака = (º або «): записують A =B (A ºB або A «B ).
Очевидно, що відношення рівносильності на множині формул є відношенням еквівалентності, тому часто це відношення називають еквівалентністю .
Наведемо приклади пар рівносильних формул:
(A ®B ) = ((ØA )ÚB ), (Ø(A ÚB )) = ((ØA )Ù(ØB )), (Ø(A ÙB )) = ((ØA )Ú(ØB )),
(A Ù(B ÚC )) = ((A ÙB )Ú(A ÙC )), (A Ú(B ÙC )) = ((A ÚB )Ù(A ÚC ))
тощо.
Ці рівносильності та подібні до них легко перевірити обчисленням таблиць істинності відповідних функцій для лівих і правих частин і порівнюванням цих таблиць.
Цей простий метод може бути застосований для перевірки рівносильності або нерівносильності будь-яких формул A і B довільної складності. Відтак, на перший погляд може здатися, що проблема встановлення рівносильності або нерівносильності формул алгебри висловлень є розв’язаною і до того ж найпростішим чином і отже, всі подальші дослідження у цьому напрямку є непотрібними.
Наведемо лише два міркування, які демонструють, що перше враження є обманливим.
Перше міркування пов’язане з тим, що коли кількість пропозиційних змінних у досліджуваних формулах є значною, то застосування зазначеного простого методу може стати практично нездійсненним. Адже, вже для 30 змінних необхідно випробувати по більш ніж 109 наборів значень змінних для кожної формули. Це тільки кількість кроків загальної процедури, а крім того, слід врахувати трудомісткість обчислення значень функцій інстинності даних формул на кожному з наборів.
По-друге, - і це міркування, певно, є важливішим, - в алгебрі висловлень у більшості випадків цікавляться не рівносильністю двох будь-яких заданих формул, а рівносильністю нескінченної множини пар формул. Потрібні твердження, згідно яких усі формули певного типу є рівносильними відповідно формулам певного іншого типу. Якщо множини формул обох цих типів є нескінченними, то подібні твердження, очевидно, не можуть бути встановлені жодним методом, що спирається на побудову таблиць інстинності, а потребують загальних міркувань.