Является ли формула тавтологией

Является ли формула тавтологией

Булевой функцией (по имени английского математика и логика Джорджа Буля) называется логическая функция, аргументы которой и она сама принимают два значения 0 и 1.

Если f(x1,…,xn) булева функция, зависящая от n аргументов, то она вполне определяется своими значениями для 2 n наборов значений аргументов. Кроме того, она вполне определяется подмножеством тех наборов, для которых она принимает значение 1. Поскольку число различных подмножеств равно , то

Теорема:Число различных булевых функций, зависящих от n аргументов равно .

Так, для n=2 число различных булевых функций равно 16. Очевидно, что всякая формула логики высказываний является булевой функцией. В дальнейшем будет показано, что и всякую булевую функцию можно интерпретировать как формулу логики высказываний.

Определение:Две формулы F и G называются равносильными, если они равны как булевы функции, т.е. принимают одинаковые значения при всех наборах значений простых компонент. Обозначается FºG.

Замечание: Формулы F и G могут содержать разные компоненты. При составлении таблицы истинности в набор включаются все компоненты, входящие в хотя бы одну из этих функций, т.е. некоторые простые компоненты могут быть фиктивными.

Тождественно-истинной (тавтологией) называется формула, таблица истинности которой состоит из одних 1 и тождественно-ложной, если все её значения равны 0. Обозначаются они соответственно Fº1 и Fº0. Если формула может принимать как значения 1, так и 0, то она называется выполнимой.

Пример:

В задаче 1 формулы b), c), d), e) — тождественно-истинные, формулы a) и f) — выполнимые.

Примером тождественно-ложной формулы будет ((aÚb)Ù(`aÙ`b)).

Отношение равносильности является отношением эквивалентности на множестве всех формул логики высказываний. Класс эквивалентности — это все формулы, соответствующие одной и той же булевой функции. Изучение булевых функций имеет большое значение как для алгебры и математической логики, так и для приложений в компьютерной математике и теории автоматов. Особую роль играют тавтологии. Проверить, является ли формула тавтологией или равносильны ли данные формулы, можно, составляя таблицы истинности. Процедура эта для большого числа аргументов утомительна или даже невозможна. Однако, существуют методы, позволяющие значительно упростить эту проверку.

Читайте также:  Брандмауэру не удалось изменить некоторые параметры 0x80070422

Наша задача в дальнейшем состоит в установлении правил равносильного преобразования формул и приведение формулы к некоторому нормальному виду

Булевой формулой называется формула, не содержащая импликации и эквиваленций.

Теорема: Всякая формула логики высказываний равносильна булевой формуле.

Доказательство этой теоремы опирается на следующие равносильности a®bº`aÚbиa«bºabÚ`a`b

Они проверяются таблицей истинности:

а b a®b `aÚb a«b abÚ`a`b

Эти равносильности имеют логический смысл.

Формула a®b означает: если верно а то верно b.

А формула `aÚb: или неверно а или верно b.

Это последнее высказывание и есть обоснование таблицы истинности для операции a®b.

Формула a«b переводится так: а верно тогда и только тогда, когда верно b, а формула abÚ`a`b означает или a и b одновременно верны , или одновременно неверны.

Сформулируем также два правила подстановки:

1. Пусть FA — формула, в которой фиксировано вхождение в неё формулы А ( в этом случае говорят, что формула А является частью формулы F , и что формула F длиннее формулы А) и пусть АºВ, тогда FА ºFВ, где в формуле F формула А заменена на формулу В.

Например F=(a®b)Ùc и A=a®b. Тогда A=a®bºB=`aÚb и (a®b)Ùcº(`aÚb)Ùc.

2. Пусть FаºGa, причём в формулах F и G фиксированы все вхождения простой компоненты а. Тогда FAºGA, где А — произвольная формула, и в формулах F и G простая компонента а заменена всюду на формулу А.

Пример. abÚ`a`bºa«b. Пусть А=c®d. Тогда (c®d)bÚ( )`bº(c®d)«b

Доказательство теоремы может быть проведено методом индукции по длине формулы с использованием указанных равносильностей, правил подстановки, а также таблицы основных равносильностей.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 9322 — | 7877 — или читать все.

Читайте также:  Конвертер субтитров в srt

Пусть дана некоторая формула F логики высказываний и надо выяснить, является ли формула F тавтологией. Простой метод доказательства – использовать таблицу истинности. Хорошо, если эта таблица небольшая, но когда высказывательных переменных много, то такой подход трудоемок. В случае, когда F имеет вид F1⊃F2, желательно использовать метод доказательства от противного. Вы предполагаете, что формула

F ложна и, делая отсюда выводы, приходите к противоречию или определяете значения переменных, при которых формула ложна. Для формул указанного вида ложность F1⊃F2 однозначно определяет: F1 – истинна, а F2 – ложна.

Пример. Является ли формула ((PQ)& P) ⊃ (Q ⊃ ¬P) тавтологией?

Решение. Предположим, что формула ((PQ) & P) ⊃ (Q ⊃ ¬P) ложна при некоторых значениях высказывательных переменных P и Q.

Получили значения переменных (Q = И и P = И), при которых формула ((PQ)& P) ⊃ (Q ⊃ ¬P) = Л, следовательно, эта формула не является тавтологией.

Равносильные формулы. Примеры равносильностей. Способы доказательств равносильностей.

Пусть A и B — две формулы и <X1, X2,…, Xn> — множество всех высказывательных переменных, входящих в формулу A и/или в формулу B. Будем называть эти формулы равносильными, если при любом распределении истинностных значений для переменных <X1, X2,…, Xn>, они принимают одинаковые значения. Равносильность формул A и B будем обозначать AB.

Теорема 1. Основные равносильности. Для любых формул A, B, C справедливы следующие равносильности:

11. ¬¬AA (снятия двойного отрицания);

  • Попроси больше объяснений
  • Следить
  • Отметить нарушение

Adelyaasakhmetova 15.10.2019

Ответ

Проверено экспертом

Ответ:

Пошаговое объяснение:

1) Пусть a=ложь, b=ложь

(¬a∧b) → (a ↔ ¬b)=(¬ложь∧ложь) → (ложь ↔ ¬ложь)=

=(истина∧ложь) → (ложь ↔ истина)=ложь → ложь=истина

Пусть a=ложь, b=истина

(¬a∧b) → (a ↔ ¬b)=(¬ложь∧истина) → (ложь ↔ ¬истина)=

=(истина∧истина) → (ложь ↔ ложь)=истина → истина=истина

Читайте также:  8Pm pst сколько по москве

Пусть a=истина, b=ложь

(¬a∧b) → (a ↔ ¬b)=(¬истина∧ложь) → (истина ↔ ¬ложь)=

=(ложь∧ложь) → (истина ↔ истина)=ложь → истина=истина

Пусть a=истина, b=истина

(¬a∧b) → (a ↔ ¬b)=(¬истина∧истина) → (истина ↔ ¬истина)=

=(ложь∧истина) → (истина ↔ ложь)=ложь → ложь=истина

2) ¬(a∧b) ↔ (¬a ∨ ¬b)=(¬a ∨ ¬b) ↔ (¬a ∨ ¬b) = истина, так как выражения в скобках эквивалентны

Ссылка на основную публикацию
Экран из фильма аватар
Джейк Салли — бывший морской пехотинец, прикованный к инвалидному креслу. Несмотря на немощное тело, Джейк в душе по-прежнему остается воином....
Что такое vpn на планшете
Каждый из пользователей интернета хоть раз да слышал о VPN, но мало кто задумывался о его необходимости и роли для...
Что такое ussd сообщение
Содержание статьи Что такое ussd запрос Как отключить GPRS-интернет Какие есть USSD-коды и полезные номера у Мегафона USSD является сокращением...
Экран ноутбука стал синим что делать
Большинство пользователей ноутбуков сталкиваются с ситуацией, когда компьютер выдает так называемый синий экран смерти или BSOD. Для начала необходимо знать:...
Adblock detector