Формули алгебри висловлювань - Студопедія

Літери, що позначають висловлювання, логічні зв'язки та дужки складаютьалфавітмов логіки висловлювань: алгебри логіки та обчислення висловлювань.

Вираз, складений із позначень висловлювань і зв'язок, – логічна формула, якщо:

– будь-яка змінна, що означає висловлювання, – формула;

також є формулами;

– інших формул, крім побудованих за правилами двох попередніх пунктів, немає.

Приклад.Подати логічною формулою наступне складне висловлювання:С– « Якщо йде дощ, то дахи мокрі. Дощу нема, а дахи мокрі».

Складне висловлюванняCвключає два простих висловлювання:А –«Йде дощ»,В –«Дахи мокрі». У першому реченні «Якщо дощ, то дахи мокрі» висловлюванняАіВз'єднані зв'язкою «якщо…, то»: . У другому реченні «Дощу ні, а дахи мокрі», союз «а» має сенс зв'язки «і», ще, висловлюванняАслід узяти з запереченням: . Для запису висловлюванняСяк формули залишається об'єднати представлені вище висловлювання однією зв'язкою «і»:С= .

Підформулоюформули називається будь-яка її частина, яка сама є формулою.

Формула називаєтьсяздійсненною (спростовною), якщо існує такий набір висловлювань, який перетворює цю формулу на справжнє (хибне) висловлювання.

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

Приклад.За допомогою таблиць істинності встановити, якими є формули та .

Складемо таблиці істинності кожної формулы:

p	r		(pÙr)
І	І	Л	І	І	Л	І
І	Л	Л	Л	І	І	І
Л	І	І	Л	Л	І	І
Л	Л	І	Л	Л	І	І

Отже, формула можна здійснити, а формула – тавтологія.

Тавтології відіграють важливу роль у логіці, на деяких з них засновані способи логічних висновків. З іншого боку, характеристики логічних операцій також виражаються через тавтології.

Теорема (властивості операції кон'юнкції та диз'юнкції).

Наступні формули є тавтологіями:

1) закони ідемпотентності:

2) закони комутативності:

3) закони асоціативності:

4) закони поглинання:

5) Закони де Моргана:

Доказ. Доведемо, що формули ідемпотентності є тавтологіями.

X
І	І	І	І	І
Л	Л	Л	І	І

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

ФормулиХіYназиваютьсярівносильними,абоеквівалентними(позначення ), якщо за будь-яких значень змінних логічні значення виходять з формулХтаYвисловлювань збігаються.

Наприклад, за таблицею істинності легко встановити, що .

Зауваження.Потрібно розрізняти символи «=» та «». Символ "" є символом логічної операції формальної мови (це необхідно і достатньо). Символ «=» не належить до алфавіту мови логіки висловлювань і говорить про рівносильність формул з погляду їх оцінювання на істинність.

Чи не знайшли те, що шукали? Скористайтеся пошуком:

Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно

---