Доказать что формула является тождественно ложной онлайн
Перейти к содержимому

Доказать что формула является тождественно ложной онлайн

  • автор:

1.6. Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости

Определение 1.3. Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И.

Определение 1.4. Формула называется тождественно-ложной, если для любых наборов переменных она принимает значение Л.

Определение 1.5. Формула называется выполнимой, если для некоторых наборов переменных она принимает значение И.

Проблема разрешимости для логики высказываний заключается в том, чтобы установить, является ли произвольная формула тождественно-истинной.

Теорема 1.1. Формула является тождественно-истинной тогда и только тогда, когда в ее КНФ в любую из элементарных дизъюнкций одновременно входят какая-либо переменная и ее отрицание.

Теорема 1.2. Формула является тождественно-ложной тогда и только тогда, когда в ее ДНФ в любую из элементарных конъюнкций одновременно входят какая-либо переменная и ее отрицание.

Следовательно, приведя формулу равносильными преобразованиями к КНФ, можно установить, является ли она тождественно-истинной, а приведя ее к ДНФ, можно установить, является ли она тождественно-ложной.

Доказать, что формула F = (АB) ((C Ú А) (C Ú B)) является тождественно-истинной.

Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(АB) ((CÚА) (CÚB)) (АB)Ú ((CА) (CÚB)) (А&B) Ú (CÚА) Ú (C Ú B)(А&B) Ú (C&А) Ú (CÚB) (А ÚC)& (АÚ А) &(BÚC) &(BÚА) Ú (CÚB) (АÚC)&(BÚC)&(BÚА)Ú (CÚB) (АÚCÚCÚB)&(BÚCÚCÚB)&(BÚАÚCÚB).

В первую дизъюнкцию входят C и C. Во вторую – B и B, C и C. в третью – B и B. Следовательно, на основании теоремы 1.1 можно утверждать, что исходная формула является тождественно-истинной.

Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями:

1) приведением с помощью равносильных преобразований к КНФ или ДНФ;

2) составлением таблицы истинности.

Установить, является ли тождественно-истинной данная формула логики высказываний: F(A, B) = (А&(АB)) B.

1) Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(А&(АB)) B (А&(АÚB)  B (А&(АÚB)  B АÚ(АÚBB АÚ(А&BB (АÚB)ÚА&B (АÚBÚА)&(АÚBÚB).

В первую дизъюнкцию входят A и A. Во вторую – B и B, поэтому формула является тождественно истинной, F(A, B)  И.

2) Составим таблицу истинности F(A, B) (таблица 1.7):

Доказать, что формулы являются тождественно ложными

Author24 — интернет-сервис помощи студентам

Являются ли тождественно истинными формулы?
Подскажите, пожалуйста, как доказать являются ли тождественно истинными формулы.

Являются ли тождественно-истинными предикатные формулы?
Выяснить, являются ли тождественно-истинными следующие предикатные формулы:(картинка в файлах) .

Являются ли тождественно-истинными предикатные формулы
Выяснить, являются ли тождественно-истинными следующие предикатные формулы: a) ∀ x R(x)& (∃xR(x).

Доказать, что формулы являются тавтологиями
Всем привет! Подскажите пожалуйста как быть с данным заданием: Спасибо

Эксперт по математике/физике

4891 / 3515 / 1137
Регистрация: 01.09.2014
Сообщений: 9,577

Алгоритм и примеры приведения к ДНФ есть на странице Википедии про ДНФ. Чтобы доказать тождественную ложность можно упрощать примерно так же, как и для приведения к ДНФ. Напишите, что у вас получается.

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Доказать, что формулы являются общезначимыми
Доказать, что формулы являются общезначимыми: перепечатайте задание на форум Добавлено через 18.

Доказать что: f(x)=g(h(x)) не тождественно g(x)=g(h(x))
В оригинале выглядит так: Допустим есть функция g, которая является функцией от h, которая в.

Доказать, что следующие формулы являются теоремами формализованного исчисления
Доказать,что следующие формулы являются теоремами формализованного исчисления высказываний,построив.

Доказать, что формула является тождественно истинной.
Нужно решить две задачи: 1)Пусть формула А не содержит никаких логических символов кроме.

Или воспользуйтесь поиском по форуму:

Таблица истинности онлайн

Данный онлайн калькулятор строит таблицу истинности для любого логического выражения. Чтобы начать, введите логическое выражение в поле ввода.

Калькулятор таблицы истинности
Примеры Очистить Ссылка
Загрузка изображения, подождите .

Составить таблицу истинности

Установить калькулятор на свой сайт

Калькулятор поддерживает следующие логические операции:

Логическая операция «не» (отрицание, инверсия)

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ¬, либо значок восклицательного знака !. Операция отрицания является унарной (содержит один операнд) и обладает наивысшим приоритетом (выполняется первой) среди логических операций.

Таблица истинности логической операции «не» имеет вид:

Логическое «и» (конъюнкция, логическое умножение)

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ∧, либо два значка амперсанда &&. Операция конъюнкция является бинарной (содержит два операнда).

Таблица истинности логической операции «и» имеет вид:

Логическое «или» (дизъюнкция, логическое сложение)

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ∨, либо два значка ||. Операция дизъюнкция является бинарной.

Таблица истинности логической операции «или» имеет вид:

Логическая операция «исключающее или» (сложение по модулю 2)

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ⊕, либо функцию .

Таблица истинности логической операции «исключающее или» имеет вид:

Логическая операция «не и» (штрих Шеффера)

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ↑, либо значок |.

Таблица истинности логической операции «не и» имеет вид:

Логическая операция «не или» (стрелка Пирса)

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ↓, либо функцию .

Таблица истинности логической операции «не или» имеет вид:

Логическая операция «эквивалентность»

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ⇔, либо конструкцию (знак меньше, знак равно, знак больше).

Таблица истинности логической операции «эквивалентность» имеет вид:

Логическая операция «исключающее не или»

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ⊙, либо функцию .

Таблица истинности логической операции «исключающее не или» имеет вид:

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

Логическая операция «импликация»

Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ⇒, либо конструкцию => (знак равно, знак больше).

Таблица истинности логической операции «импликация» имеет вид:

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

Другие полезные разделы:

Оставить свой комментарий:

Мы в социальных сетях:
Группа ВКонтакте | Бот в Телеграмме

© Mathforyou 2024
Контакты: support@mathforyou.net

Таблица истинности

Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис.
Для булевой функции, заданной вектором значений (например, 00111011 ) используйте ввод данных через таблицу.

Видеоинструкция

Правила ввода логической функции
  1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
  2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
  3. Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики — алгебры логики. В алгебре логики можно выделить три основные логические функции: «НЕ» (отрицание), «И» (конъюнкция), «ИЛИ» (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:

  • словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
  • описание функции алгебры логики в виде таблицы истинности.
  • описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
    а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
    1) в таблице выбираются те строки переменных для которых функция на выходе =1 .
    2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
    3) полученное произведение логически суммируется.
    Fднф= X 123 ∨ Х1 x 2Х3 ∨ Х1Х2 x 3 ∨ Х1Х2Х3
    ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
    б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
    КНФ может быть получена из таблицы истинности по следующему алгоритму:
    1) выбираем наборы переменных для которых функция на выходе =0
    2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
    3) логически перемножаются полученные суммы.
    Fскнф=(X1 V X2 V X3) ∧ (X1 V X2 V X 3) ∧ (X1 V X 2 V X3) ∧ ( X 1 V X2 V X3)
    КНФ называется совершенной, если все переменные имеют одинаковый ранг.

По алгебраической форме можно построить схему логического устройства, используя логические элементы.

Рисунок1- Схема логического устройства Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Операция НЕ — логическое отрицание (инверсия)

  • если исходное выражение истинно, то результат его отрицания будет ложным;
  • если исходное выражение ложно, то результат его отрицания будет истинным.
A не А
0 1
1 0

Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.

Операция ИЛИ — логическое сложение (дизъюнкция, объединение)

Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Применяемые обозначения: А или В, А V В, A or B, A||B.
Результат операции ИЛИ определяется следующей таблицей истинности:

A B А или B
0 0 0
0 1 1
1 0 1
1 1 1

Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны.

Операция И — логическое умножение (конъюнкция)

Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Применяемые обозначения: А и В, А Λ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:

A B А и B
0 0 0
0 1 0
1 0 0
1 1 1

Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.

Операция «ЕСЛИ-ТО» — логическое следование (импликация)

Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.
Применяемые обозначения:
если А, то В; А влечет В; if A then В; А→ В.
Таблица истинности:

A B А → B
0 0 1
0 1 1
1 0 0
1 1 1

Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Применяемое обозначение: А ↔ В, А ~ В.
Таблица истинности:

A B А↔B
0 0 1
0 1 0
1 0 0
1 1 1

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

Операция «Сложение по модулю 2» (XOR, исключающее или , строгая дизъюнкция)

Применяемое обозначение: А XOR В, А ⊕ В.
Таблица истинности:

A B А⊕B
0 0 0
0 1 1
1 0 1
1 1 0

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

Приоритет логических операций

  • Действия в скобках
  • Инверсия
  • Конъюнкция ( & )
  • Дизъюнкция ( V ), Исключающее ИЛИ (XOR), сумма по модулю 2
  • Импликация ( → )
  • Эквивалентность ( ↔ )

Совершенная дизъюнктивная нормальная форма

  1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x1,x2. xn).
  2. Все логические слагаемые формулы различны.
  3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
  4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Совершенная конъюнктивная нормальная форма

  1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x1,x2. xn).
  2. Все элементарные дизъюнкции различны.
  3. Каждая элементарная дизъюнкция содержит переменную один раз.
  4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.

Налоговый вычет на обучение

√ 120 тыс. руб. — максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя

Требуются авторы студенческих работ!

  • регулярный поток заказов;
  • стабильный доход

Учебно-методический

  • курсы переподготовки и повышения квалификации;
  • вебинары;
  • сертификаты на публикацию методического пособия

  • Задать вопрос или оставить комментарий
  • Помощь в решении
  • Поиск
  • Поддержать проект

Правила ввода данных

Задать свои вопросы или оставить замечания можно внизу страницы в разделе Disqus .
Можно также оставить заявку на помощь в решении своих задач у наших проверенных партнеров (здесь или здесь).

Поиск

Задать свои вопросы или оставить замечания можно внизу страницы в разделе Disqus .
Можно также оставить заявку на помощь в решении своих задач у наших проверенных партнеров (здесь или здесь).

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *