Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2019-05-27 | 3143 |
5.00
из
|
Заказать работу |
|
|
С помощью таблиц истинности можно установить эквивалентность двух или нескольких высказываний.
Высказывания называются эквивалентными, если соответствующие значения каждого из них совпадают в таблице истинности.
Если значения сложных высказываний совпадают на всех наборах значений входящих в них переменных, то такие высказывания называют равносильными, или тождественными, или эквивалентными.
Примеры решения задач
Пример 1
Утверждается, что высказывание А+В· С эквивалентно высказыванию (А+В)·(А+С).Проверить это утверждение.
Решение. Проверка ведется путем составления таблицы истинности.
А | В | С | В· С | А+В· С | А+В | А+С | (А+В)· (А+С) |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Сравнивая 5-ю и 8-ю колонки, убеждаемся, что все значения, получаемые по формуле А+В·С, совпадают со значениями, получаемыми по формуле (А+В)·(А+С), т. е. высказывания эквивалентны (равносильны). Одно может заменить другое.
Эквивалентные (равносильные) высказывания соединяют знаком º
А + В× Сº(А+В)· (А+С).
Отметим различие между эквивалентностью и эквиваленцией.
Эквиваленция является логической операцией, позволяющей по двум заданным высказываниям А и В построить новое А«В.
Эквивалентность же является отношением между двумя составными высказываниями, состоящим в том, что их значения истинности всегда одни и те же.
Пример 2
Эквивалентны ли высказывания:
и
Решение.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
А | В | С | |||||||
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
Вывод.
|
Высказывание () и высказывание () не эквивалентны.
Тавтология
Пусть дано высказывание А × А и необходимо составить таблицу истинности.
А | А× | |
1 | 0 | 0 |
0 | 1 | 0 |
Высказывание А × ложно, истинность его не зависит от истинности высказывания А.
Рассмотрим высказывание В+ .
В | В+ | |
1 | 0 | 1 |
0 | 1 | 1 |
В этом случае высказывание В + всегда истинно, независимо от истинности В.
Высказывания, истинность которых постоянна и не зависит от истинности входящих в них простых высказываний, а определяется только их структурой, называются тождественными.
Различают тождественно-истинные и тождественно-ложные высказывания.
Если высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1)
Если высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0)
В формулах каждое тождественно-истинное высказывание заменяется 1, а тождественно-ложное – 0. Закон исключенного третьего. A× º0 В+ º1
Примеры решения задач
Пример 1
Докажите тавтологию (XÙY)®(XÚY).
Решение
X | Y | XÙY | XÚY | (XÙY)®(XÚY) |
0 | 0 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 1 |
Пример 2
Докажите тавтологию ((X®Y)Ù(Y®Z))®(X®Z).
Решение
F1 F2 F3
X | Y | Z | X®Y | Y®Z | X®Z | F1ÙF2 | (F1ÙF2) ®F3 |
0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Вывод. Высказывание ((X®Y)Ù(Y®Z))®(X®Z) является тавтологий (тождественно-истинное высказывание).
|
Пример 3
Установить является ли данное высказывание тавтологией.
A | B | AÙB | |||||
0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
Вывод. Высказывание является тавтологией
Классификация высказываний
· тавтологии (тождественно истинные);
· тождественно ложные;
· эквивалентные.
Пример. Из простых высказываний: “Виктор хороший пловец” – А; “Виктор хорошо ныряет” – В; “Виктор хорошо поет” – С, составлено сложное высказывание, формула которого имеет вид: X=(AÚC)Ù(AÚB). Установить, эквивалентно ли высказывание Х высказыванию: “Виктор – хороший пловец и Виктор хорошо поет”.
Решение. Y=AÙC
1 | 2 | 3 | 4 | 5 | 6 | 7 |
А | В | С | AÚC | AÚB | X | Y=AÙC |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 1 | 0 |
1 | 0 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 1 |
Вывод. Высказывание X не эквивалентно высказыванию Y.
СДНФ и СКНФ
На практике при конструировании различных электронных устройств часто возникает задача – от таблицы истинности перейти к формуле, чтобы на ее основе построить функциональную схему. Переменные структурной формулы соответствуют входам функциональной схемы. Значения переменных в таблице истинности соответствуют значениям входов функциональной схемы.
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.
Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ).
Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (КНФ).
Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).
Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).
|
|
|
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!