У нашій онлайн базі вже 23510 рефератів!

Навігація
Перелік розділів
Найпопулярніше
Нові реферати
Пошук
Замовити реферат
Додати реферат
В вибране
Контакти
Російські реферати
Статьи
Об'яви
Новини
На сайті всього 23510 рефератів!
Ласкаво просимо на UA.TextReferat.com
Реферати, курсові і дипломні українською мовою, які можна скачати цілком або переглядати по сторінкам.

Усе доступно безкоштовно, тому ми не платимо винагороди за додавання. Авторські права на реферати належать їх авторам.

Алгебра висловлень

Сторінка 2

Функцію f називають функцією істинності для формули A або відповідного складеного висловлення. Для функції істинності може бути побудована так звана таблиця істинності цієї функції (див.таблицю 3).

Таблиця 3

p1 p2 pn-1 pn

f (p1,p2, .,pn-1,pn)

0 0 . 0 0

0 0 . 0 1

0 0 . 1 0

0 0 . 1 1

.

1 1 . 1 0

1 1 . 1 1

f (0,0, .,0,0)

f (0,0, .,0,1)

f (0,0, .,1,0)

f (0,0, .,1,1)

.

f (1,1, .,1,0)

f (1,1, .,1,1)

Серед формул алгебри висловлень особливе місце займають ті формули A(p1,p2, .,pn), які на всіх наборах (a1,a2, .,an) значень своїх змінних набувають значення 1.

Формула алгебри висловлень A(p1,p2, .,pn) називається тавтологією тоді і тільки тоді, коли їй відповідає функція істинності, яка тотожно дорівнює 1.

Тавтології ще називають тотожно істинними формулами, або законами алгебри висловлень. Аналогом тавтології у природній мові є поняття істинного твердження.

Наведемо приклади деяких важливих тавтологій:

(pÚ(Øp)) (закон виключення третього),

(Ø(pÙ(Øp))) (закон виключення суперечності),

(p®p) (закон тотожності).

Довести, що ці формули є тавтологіями можна за допомогою відповідних таблиць істинності. Той факт, що формула A алгебри висловлень є тавтологією позначають так |=A. Символ |=, як і A належать метамові.

Формула алгебри висловлень A(p1,p2, .,pn), яка набуває значення 0 на всіх наборах (a1,a2, .,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 наборів значень змінних для кожної формули. Це тільки кількість кроків загальної процедури, а крім того, слід врахувати трудомісткість обчислення значень функцій інстинності даних формул на кожному з наборів.

По-друге, - і це міркування, певно, є важливішим, - в алгебрі висловлень у більшості випадків цікавляться не рівносильністю двох будь-яких заданих формул, а рівносильністю нескінченної множини пар формул. Потрібні твердження, згідно яких усі формули певного типу є рівносильними відповідно формулам певного іншого типу. Якщо множини формул обох цих типів є нескінченними, то подібні твердження, очевидно, не можуть бути встановлені жодним методом, що спирається на побудову таблиць інстинності, а потребують загальних міркувань.

Зокрема, однією з основних проблем алгебри висловлень є проблема опису класу всіх тавтологій (тобто тотожно істинних формул), яка носить назву проблеми розв’язності. Простішим варіантом цієї проблеми є така: вказати правило перевірки скінченним числом дій тотожної істинності певної формули.

Проблема розв’язності займає важливе місце в математичній логіці. До проблеми розв’язності зводиться багато різних задач математичної логіки.

Наприклад, до проблеми розв’язності може бути зведена обговорювана вище проблема перевірки рівносильності заданих формул A і B.

Легко довести таку теорему.

Теорема 1. Формули алгебри висловлень A і B рівносильні тоді і тільки тоді, коли формула ((A®B)Ù(B®A)) є тавтологією.

З метою скорочення запису формул, подібних до формули з наведеної теореми, до сигнатури алгебри висловлень вводять додаткову операцію, що позначається ~ і означається так: (A~B) є скороченим записом формули ((A®B)Ù(B®A)).

Отже, останню теорему можна сформулювати так.

Формули A і B рівносильні тоді і тільки тоді, коли формула (A~B) є тотожно істинною.

Разом з відношенням рівносильності на множині формул алгебри висловлень, яке є, як зазначалось, відношенням еквівалентності, розглядають також деякі інші відношення, що являють собою інтерес для логіки та її застосувань. Серед останніх виділимо відношення логічного слідування, яке є відношенням часткового порядку на множині формул алгебри висловлень.

Нехай A(p1,p2, .,pn) і B(p1,p2, .,pn) - дві формули алгебри висловлень. Будемо говорити, що формула B(p1,p2, .,pn) є логічним слідуванням формули A(p1,p2, .,pn), якщо B приймає значення 1 для всіх тих наборів значень пропозиційних змінних, для яких формула A істинна (тобто приймає значення 1); позначатимемо це AÞB.

Це означає, що множина наборів значень змінних, для яких істинна формула A, є підмножиною множини наборів значень змінних, для яких істинна формула B, що є логічним слідуванням формули A.

Приклад 5.1. Формула B(x,y,z)=(xÚz) є логічним слідуванням формули A(x,y,z)=((xÚy)Ùz) , що випливає з відповідних таблиць істинності (див.табл.4).

Таблиця 4

x y z

A B

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

0 0

0 1

0 0

1 1

0 1

1 1

0 1

1 1

Очевидно, що дві формули A і B є рівносильними тоді і тільки тоді, коли кожна з них є логічним слідуванням іншої, тобто A=B тоді і тільки тоді, коли AÞB і BÞA.

З означення випливає також, що будь-яка формула є логічним слідуванням тотожно хибної формули, а тотожно істинна формула (тавтологія) є логічним слідуванням довільної формули.

Проблема перевірки чи є формула B логічним слідуванням іншої заданої формули A також може бути зведена до проблеми розв’язності для певної формули алгебри висловлень.

Теорема 2. Формула B(p1,p2, .,pn) є логічним слідуванням формули A(p1,p2, .,pn) тоді і тільки тоді, коли тотожно істинною є формула (A®B).

1 [2] 3

завантажити реферат завантажити реферат
Нове
Цікаві новини

Замовлення реферату
Замовлення реферату

Лічильники

Rambler's Top100

Усі права захищено. @ 2005-2019 textreferat.com