Вариант 1 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 2 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 3 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 4 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 5 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 6 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 7 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 8 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 9 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 10 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 11 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 12 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 13 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 14 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 15 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 16 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 17 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 18 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 19 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 20 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 21 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 22 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 23 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 24 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 25 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 26 Составить таблицы истинности для следующих логических выражений: ; . |
Вариант 27 Составить таблицы истинности для следующих логических выражений: ; . | Вариант 28 Составить таблицы истинности для следующих логических выражений: ; . |
В | |||||
0 | 0 | 1 | 1 | ||
0 | 1 | 0 | 1 | ||
1 | 0 | 0 | 0 | ||
1 | 1 | 0 | 1 | В | С |
0 | 0 | 0 | 1 | 0 | 0 |
0 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | |
1 | 0 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 1 |
Алгоритм построения таблицы истинности
При построении таблицы истинности целесообразно руководствоваться определенной последовательностью действий.
1. Определите количество строк в таблице. Если количество логических переменных равно n, то количество строк = 2n.
2. Определите количество столбцов, которое будет равно количеству переменных + количество логических операций.
3. Постройте таблицу, заполните шапку и внесите возможные наборы значений исходных логических переменных.
4. Заполните таблицу истинности по столбцам, выполняя базовые логические операции в необходимой последовательности.
Пример 1.
Для формулы A & (B V C) построить таблицу истинности. Количество логических переменных 3, следовательно, количество строк – 23 = 8. Количество логических операций в формуле – 2.
Количество столбцов равно 2 + 3 = 5. Далее строим таблицу истинности по заданному алгоритму.
Таблица 13 -Таблица истинности
| A | B | C | B V C | A & (B V C) |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Исходные данные
1. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (табл. 14).
Таблица 14 -Фрагмент таблицы истинности выражения F
| X | Y | Z | F |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
Какое выражение соответствует F:
a) X V Y V Z;
b) X & Y & Z;
c) X & Y & Z;
d) X V Y V Z.
Для того чтобы определить, какое выражение соответствует F, необходимо составить фрагменты таблиц истинности для всех приведенных вариантов.
2. По заданному преподавателем варианту из таблицы 15 составить таблицу истинности для заданной формулы. При каких значениях A, B. C логическое выражение будет истинным?
Таблица 15- Выбор исходных данных
| Номер варианта | Значение формулы |
| 1 | A & (C V B) |
| 2 | C V (A V B) |
| 3 | A & (B V C) |
| 4 | A V (C V B) |
| 5 | A & B V C |
| 6 | C V (A V B) |
| 7 | A & (C V B) |
| 8 | B & (A V C) |
| 9 | B & (C V A) |
| 10 | A & (C V B) |
Содержание отчета
1. Номер, название темы практического занятия.
2. Цель практического занятия.
3. Результаты выполнения работы: построение таблиц истинности.
4. Выводы по работе.
Контрольные вопросы
1. Перечислите основные логические операции.
2. Заполните таблицы истинности для следующих логических операций: логического отрицания, дизъюнкции, конъюнкции.
3. Поясните, в каком случае строится таблица истинности.
4. Скажите, чему равно количество строк в таблице истинности.
5. Скажите, чему равно количество столбцов в таблице истинности.
6. Сформулируйте алгоритм заполнения таблицы истинности для сложной логической формулы.
Практическая работа 4
«Построение логических схем по заданным выражениям»
Цель: изучить основные логические элементы, научиться строить логические схемы по заданным логическим выражениям.
Теоретические сведения
Основой всех компьютерных устройств, построенных по цифровому принципу, являются логические элементы – преобразователи. Логические элементы (преобразователи) могут, получая сигналы об истинности отдельных простых высказываний, обработать их и в результате выдать значение логического произведения или логической суммы, или отрицания. Логический элемент – это электронное устройство, выполняющее соответствующую логическую функцию.
Из логических элементов (вентилей) составляют более сложные схемы, которые позволяют выполнять арифметические операции и хранить информацию. Процесс разработки общей логической схемы устройства (в том числе и компьютера в целом), становится иерархическим, причем на каждом следующем уровне в качестве
«кирпичиков» используются логические схемы, созданные на предыдущем этапе.
Логический элемент И реализует конъюнкцию двух или более логических значений (табл. 16).
Таблица 16 -Логический элемент И
| X | Y | X & Y |
| 0 | 0 | 0 | |
| 1 | 0 | 0 | |
| 0 | 1 | 0 | |
| 1 | 1 | 1 |
Логический элемент ИЛИ реализует дизъюнкцию двух или более логических значений (табл. 17).
Таблица 17-Логический элемент ИЛИ
| X | Y | X V Y |
| 0 | 0 | 0 | |
| 1 | 0 | 1 | |
| 0 | 1 | 1 | |
| 1 | 1 | 1 |
Логический элемент НЕ реализует логическую функцию
«инверсия» (табл. 18).
Таблица 18 -Логический элемент НЕ
| X | Y |
| 0 | 1 | |
| 1 | 0 |
Построение таблиц истинности для логических выражений — 8 КЛАСС ► Информатика в школе и дома
Для логического выражения можно построить таблицу истинности, показывающую, какие значения принимает выражение при всех наборах значений входящих в него переменных.
Для построения таблицы истинности следует:
- Подсчитать n — число переменных в выражении;
- Подсчитать общее число логических операций в выражении;
- Установить последовательность выполнения логических операций с учётом скобок и приоритетов;
- Определить число столбцов в таблице: число переменных + число операций;
- Заполнить шапку таблицы, включив в неё переменные и операции в соответствии с последовательностью, установленной в п. 3;
- Определить число строк в таблице (не считая шапки таблицы): m=2n;
- Выписать наборы входных переменных с учётом того, что они представляют собой целый ряд n-разрядных двоичных чисел от 0 до 2n−1;
- Провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью.
Построим таблицу истинности A∨A&B. В нём две переменные, две операции, причём сначала выполняется конъюнкция, а затем дизъюнкция. Всего в таблице будет четыре столбца:
Наборы входных переменных — это целые числа от 0 до 3, представленные в двухразрядном двоичном коде: 00,01,10,11. Заполненная таблица истинности имеет вид:
A | B | A&B | A∨A&B |
0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 |
1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 |
Обрати внимание!
Последний столбец (результат) совпал со столбцом A. В таком случае говорят, что логическое выражение A∨A&B равносильно логической переменной A.
Приоритет логических операций При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету: инверсия конъюнкция дизъюнкция импликация и эквивалентность.Для изменения порядка действий используются скобки.
Подробно разобран пример составления и работы с таблицей истинности в презентации ниже. Смотрите и скачивайте бесплатно.
3 ключевые приемы создания таблиц истинности
Таблицы истинности датируются 1902 годом логиком Чарльзом Сандерсом Пирсом, который использовал их как метод отображения алгебраической логики. Таблицы истинности эволюционировали с годами. Поскольку все больше людей полагаются на них для представления логических результатов, они стали более полезными в других областях и теперь играют важную роль в бизнес-процессах и автоматизации.
Что такое таблица истинности?
Таблица истинности — это, по сути, правило, представленное в виде таблицы.Однако эти таблицы — это нечто большее, чем просто базовое определение. Они представляют собой способ представления информации и логической последовательности действий входных данных.
Таблицы истинности встроены в Excel как таблицы со строками и столбцами. В верхней части таблицы, в заголовках столбцов, находятся условия, на которых основано правило, выраженные в структуре существительного / глагола.
Например, если вы должны создать таблицу истинности, которая извлекает тип автомобиля из списка производителей автомобилей, у вас может быть столбец с заголовком «CarType In List.«CarType» будет существительным, а «Contains» — глаголом. Строки ниже будут отображать различные типы автомобилей. Важно отметить, что таблица истинности позволяет сравнивать все возможные комбинации из нескольких входных данных; он не ограничивается вводом из одного столбца.
Это помогает предприятиям, позволяя таблице истинности замкнуть цикл с выходом. Последний столбец в таблице истинности выражает результат после сбора данных из входа или входов.Выходные данные могут быть другим фрагментом данных или могут быть инструкциями о том, какое действие следует предпринять, вызывая поток. Так же, как они могут обрабатывать несколько входных данных, таблицы истинности могут возвращать более одного результата.
Ключевые приемы построения таблиц истинности
Использование математических методов в традиционных таблицах истинности может затруднить их использование с точки зрения бизнеса. Однако если посмотреть на таблицы истинности как на способ определения логических результатов, легче увидеть, как они применяются к автоматизации бизнеса и процессов.Такое мышление поможет вам понять некоторые ключевые приемы, которые упростят создание и использование таблиц истинности, чтобы вы могли использовать их для облегчения потоков и автоматизации бизнес-процессов.
1. Понимание различных типов вывода.
Первый трюк при построении таблиц истинности состоит в том, чтобы понять различные типы вывода:
- Правило возврата данных (одиночное) возвращает одну переменную в поток.
- Правило возврата данных (множественное) возвращает несколько переменных в поток.
- Составной тип для случаев, когда у вас есть несколько выходов в таблице истинности, если вы хотите получить доступ к каждому выходу индивидуально, а не как к объекту.
- Правило действия передает значение и выполняет поток.
Понимание различных типов правил позволяет вам лучше понять концепцию того, что вы можете делать с таблицами истинности и правила, которые вы создаете с ними.
2. Понять, как таблицы истинности автоматизируют потоки
Это чрезвычайно полезно, когда вам нужно проанализировать данные из различных входных данных и принять решение на основе оценки этих данных.На основе оценки входных данных таблица истинности может выводить решение «да» или «нет», предоставлять ориентировочную стоимость или запрашивать дополнительную информацию. Это может быть полезно, если вы пытаетесь автоматизировать процесс самообслуживания для конечных пользователей. Таблицы истинности также дают вам возможность направлять информацию на утверждение или автоматизировать ввод данных на основе оценки входных данных. Например, если ввод красный, данные могут быть отправлены одному отделу или человеку для утверждения. Если поле ввода синее, данные будут перемещены в другой отдел или другого человека.
3. Можно использовать внешние таблицы истинности
Не все таблицы истинности требуют ручного ввода данных. Фактически, данные внешней таблицы истинности — это распространенный метод заполнения столбцов таблицы истинности. Электронные таблицы Excel, файлы CSV, базы данных и даже данные из веб-службы или очереди сообщений могут заполнять входные данные таблиц истинности, что позволяет таблице истинности собирать информацию из внешних источников, чтобы избежать дублирования ввода данных. Это не только экономит время, но и сохраняет единый источник истины, поскольку данные из внешней таблицы истинности должны редактироваться в источнике, а не в самой таблице истинности.Зарегистрируйтесь, чтобы посмотреть наш недавний веб-семинар по внешним таблицам истинности здесь.
Как программное обеспечение Decisions помогает вам с таблицами истинности
Когда дело доходит до таблиц истинности, вам нужно решение, которое максимально упрощает не только их построение, но и превращение вывода в автоматизированные потоки.
Вот где решения имеют значение.
Когда дело доходит до построения таблиц истинности, мастер, предоставляемый программным обеспечением, позволяет легко установить ваши утверждения вверху, чтобы создать условия существительного / глагола вместе со столбцами, которые определяют, что происходит с выводом.Автоматизацию легко встроить в ваши таблицы истинности, используя тот же простой в использовании мастер. Сообщите программе, что вы хотите сделать с выходными данными, и это поможет вам создать этот автоматизированный поток.
Поддержка внешних таблиц истинности дополняет преимущества использования Decisions для создания таблиц истинности, которые помогают вашему бизнесу двигаться более эффективно и результативно. Если вы хотите обсудить свой конкретный вариант использования, мы будем рады услышать об этом. Свяжитесь с нами по адресу [email protected].
таблиц истинности · Темы GitHub · Таблицы истинности GitHub
· Темы GitHub · GitHubЗдесь 14 публичных репозиториев в соответствии с этой темой…
xFunc — это простое и удобное приложение, которое позволяет создавать математические и логические выражения. Написано на C #. В библиотеке есть код, преобразующий строки в выражения (парсер, лексер и т. Д.)
генератор таблицы истинности — это инструмент, который позволяет генерировать таблицу истинности
- Обновлено 24 сен.2021
- Блокнот Jupyter
крошечный синтаксический анализатор и решатель выражений логической алгебры (иногда он может даже упрощать выражения)
- Обновлено 21 мая 2021 г.
- Python
Утилита для создания таблиц истинности из простых выражений
- Обновлено 30 нояб.2019 г.
- Юлия
Приложение для создания таблицы истинности, написанное на JavaScript с использованием Mithril
- Обновлено 29 сен.2021
- JavaScript
Двухразрядный умножитель с дополнением до двух, разработанный в Proteus
Печатайте красиво отформатированные таблицы истинности из любого логического выражения!
- Обновлено 23 апреля 2021 г.
- Python
Построитель таблицы истинности логических выражений
генерирует таблицу истинности из логического выражения
- Обновлено 9 апреля 2018 г.
- Python
Создание таблиц истинности из логических выражений в исходном коде Python
- Обновлено 23 июня 2017 г.
- Python
Создайте граф перехода состояний (автомат Мура) из таблицы истинности, имеющей текущее состояние и значения следующего состояния.
Проблемы конвейерной обработки и синхронизации в путях данных ЦП. Принципы набора команд и архитектуры процессора RISC-типа. Структурные риски, риски данных и управления в процессоре RISC, петли пересылки, механизмы ветвления. Архитектуры памяти в ЦП, такие как файлы регистров и кеши. Протоколы UART, I2C.
- Обновлено 12 февраля 2021 г.
- HTML
Утилита для создания таблиц истинности из простых выражений
- Обновлено 30 нояб.2019 г.
- Юлия
📖 Инструмент Python для таблиц истинности
- Обновлено 25 декабря 2019 г.
- Python
Улучшить эту страницу
Добавьте описание, изображение и ссылки на таблицы истинности страницу темы, чтобы разработчикам было легче узнать о ней.
Куратор этой темы
Добавьте эту тему в свое репо
Чтобы связать ваш репозиторий с таблицы истинности тема, посетите целевую страницу репо и выберите «управлять темами».
Учить больше
Вы не можете выполнить это действие в настоящее время.Вы вошли в систему с другой вкладкой или окном. Перезагрузите, чтобы обновить сеанс. Вы вышли из системы на другой вкладке или в другом окне. Перезагрузите, чтобы обновить сеанс.Реализуйте таблицу истинности — Simulink
Вы указываете матрицу, которая определяет все возможные выходы блока как Таблица истинности параметр. Каждая строка матрицы содержит вывод для другой комбинации входных элементов.Вы должны укажите выходы для каждой комбинации входов. Количество столбцов количество выходов блока.
Параметр Таблица истинности может иметь логические значения (0
или 1) любого типа данных, включая типы данных с фиксированной точкой. Если таблица
содержит не-логические значения, тип данных таблицы должен быть двойной .
Связь между количеством входов и количеством строк это:
количество строк = 2 (количество
входы)
Simulink ® возвращает строку матрицы путем вычисления индекса строки из
элементы входного вектора.Simulink вычисляет индекс, создавая двоичное число, где ввод
элементы вектора, имеющие нулевые значения, равны 0, а элементы, имеющие ненулевые значения
равны 1, затем прибавляем 1 к результату. Для входного вектора у , из м элементов:
индекс строки = 1 +
u (м) * 2 0 +
u (м-1) * 2 1 +... +
u (1) * 2 м-1
Программное использование
Параметр блока : TruthTable |
| Тип : вектор символов |
| Значения : матрица |
По умолчанию : '[0 0; 0 1; 0
1; 1 0; 0 1; 1 0; 1 0; 1 1] ' |
Понимание внешних таблиц истинности: приложения для вашего бизнеса — BPI
Таблицы истинности используются для визуальной организации информации при рассмотрении всех возможных результатов и сценариев из предоставленных предпосылок.Хотя таблицы истинности наиболее распространены в математике, они также используются в информатике, электротехнике и даже философии. Учитывая широкий спектр использования таблиц истинности, неудивительно, что они применяются также и к рабочим процессам и бизнес-процессам.
В деловом мире таблица истинности — это правило, представленное в виде таблицы, которая сравнивает возможные результаты различных входных данных в вашем решении по автоматизации бизнес-процессов и запускает рабочие процессы на основе выходных данных.
Вот простой пример: покупатель вводит заказ на 1000 красных кружек. Таблица истинности будет анализировать входные кружки, красный цвет и 1000, чтобы увидеть, достаточно ли этого конкретного предмета на складе. Затем рабочий процесс может исходить из вашей таблицы истинности, требующей, чтобы заказы на более чем 1000 штук получали одобрение от кого-либо в вашей организации или требовали ЗП или частичную оплату. Затем рабочий процесс направляется соответствующему утверждающему для дальнейших действий.
Зачем нужна внешняя таблица истинности?
При использовании внешней таблицы истинности строки или значения берутся из отчета вне программного обеспечения для автоматизации бизнес-процессов.Этот отчет может быть получен из файла Excel, файла .csv, базы данных или даже веб-службы или очереди сообщений. Поскольку этот тип таблицы истинности создается вне вашего решения по автоматизации бизнес-процессов, вы не можете редактировать ее на своей платформе автоматизации бизнеса. Чтобы внести какие-либо изменения, вам нужно будет отредактировать источник входных данных, а затем вернуть его в виде отчета.
Так зачем вам использовать внешние данные из таблицы истинности, которую вы не создали сами, при автоматизации бизнес-процесса? На самом деле есть несколько причин, почему.
Для начала, вы можете работать с большим набором правил. У вас может быть база данных с тысячами записей, с которыми вам нужно работать. В этом случае восстановление таблицы истинности самостоятельно будет утомительным занятием. Вы можете сэкономить немало времени, используя внешнюю таблицу истинности из отчета базы данных.
Еще одна причина, по которой вы можете захотеть полагаться на внешнюю таблицу истинности, — это если вы работаете с данными, которые растут или изменяются иным образом. Например, если вы работаете с данными из своего решения для управления взаимоотношениями с клиентами (CRM), вы можете создавать отчеты для использования в качестве таблиц истинности.Решения CRM постоянно растут и меняются в зависимости от охвата клиентов и кампаний. Создание новой таблицы истинности с нуля означало бы потерю драгоценного времени, которое вы могли бы потратить на анализ этих данных. Каждый раз, когда вы знаете, что количество правил изменится или вырастет, вы захотите полагаться на данные, полученные из отчетов, которые вы постоянно запускаете, чтобы получить самые свежие данные.
Использование внешних таблиц истинности также дает вам единый источник истины для работы. Если вы перестраиваете таблицу истинности на основе правил веб-службы, вам придется редактировать эту таблицу истинности каждый раз, когда происходит изменение.Если вы сделаете ошибку при редактировании, у вас будет два разных набора данных. Если вы забудете или не сможете обновить таблицу истинности, у вас будут другие наборы данных. Если вы запустите отчет из своих веб-служб и внесете эти данные в программное обеспечение для автоматизации бизнес-процессов в виде внешней таблицы истинности, ваши данные останутся согласованными и точными.
Таблицы истинностипредлагают вам возможность представлять правила в ваших бизнес-процессах, определять условия и отображать результаты в виде легкого для понимания визуального артефакта.Чтобы увидеть, насколько легко работать с таблицами истинности, потратьте несколько минут на просмотр этих видеороликов. Чтобы получить более подробное представление о том, как использовать таблицы истинности с акцентом на внешние таблицы истинности, зарегистрируйтесь для просмотра этого вебинара. Вебинар посвящен таблицам истинности и их использованию, а также способам построения таблиц истинности и способам использования внешних таблиц истинности при необходимости.
Сообщение «Понимание внешних таблиц истинности: приложения для вашего бизнеса» впервые появилось в блоге «Решения».
Создание таблиц истины — обучающие машины
Коротко на сегодня: в этом посте мы узнаем, как легко создать таблицы истинности с помощью R, и добавим наш код в растущий репозиторий Rosetta code .Я надеюсь, что по пути вы научитесь нескольким трюкам, так что читайте дальше!
Мы уже рассмотрели фрагменты кода, который я внес в Rosetta Code в этом блоге ранее (см. Категория: Rosetta Code). На этот раз мы хотим решить следующую задачу:
Таблица истинности
Таблица истинности — это отображение входов и выходных данных логической функции, организованной в виде таблицы, где каждая строка дает одну комбинацию входных значений и соответствующее значение функции.Задача
- Введите логическую функцию от пользователя в виде строки, затем вычислите и распечатайте отформатированную таблицу истинности для данной функции.
(можно предположить, что пользовательский ввод правильный).% D)) ## 1 ЛОЖЬ ЛОЖЬ ЛОЖЬ ЛОЖЬ ## 2 ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ## 3 ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ ИСТИНА ## 4 ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ## 5 ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ## 6 ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ ## 7 ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ ## 8 ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ## 9 ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ИСТИНА ## 10 ИСТИНА ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ ## 11 ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ## 12 ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА ## 13 ЛОЖЬ ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ ## 14 ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА ИСТИНА ## 15 ЛОЖЬ ИСТИНА ИСТИНА ИСТИНА ИСТИНА ## 16 ИСТИНА ИСТИНА ИСТИНА ИСТИНА ЛОЖЬВыглядит хорошо! Полный код также можно найти здесь: Rosetta Code: Truth Table: R.
Подозреваю, что эта функция пригодится для решения дальнейших задач в будущем, так что следите за обновлениями!
таблиц истинности | Введение в Logic
Таблицы истинности отображают все значения истинности, которые могут иметь данное утверждение или набор утверждений. Это означает, что то, знаем ли мы для любого данного утверждения, что оно истинно или ложно, не мешает нам узнать о нем какие-то другие вещи по сравнению с некоторыми другими утверждениями.Разве это не было полезным разъяснением?
Но давайте вернемся немного назад.
В предыдущем разделе мы представили определения операторов с помощью функций истинности. Имея эту информацию (представленную в таблицах истинности, в которых показаны все возможные значения «p» и «q»), у нас есть достаточно информации, которую мы можем «вычислить» или выяснить истинность составных утверждений, пока мы знаем истинность простых утверждений, из которых они состоят.
Например, поскольку мы знаем, что
Бананы фруктовые верно
и Яблоки фрукты правда
и Груши фруктовые правда,
мы можем выяснить, что это утверждение:
Б (A ∙ ~ P)
— ложь.
Как? Перечислите значения истинности под буквами, а затем объедините значения в соответствии с определениями пяти операторов, начиная с наименьшей единицы и заканчивая наибольшей.
B ⊃ (А ∙ ~ П) т Т FT В этой таблице показаны значения этих трех операторов.Все они верны, поэтому под каждым утверждением стоит буква «Т»; и поскольку происходит отрицание «Груши — это фрукты» («Груши — не фрукты»), у нас есть «F» под тильдой.
Простейший или наименьший уровень, на котором могут быть выполнены любые «вычисления», — это отрицание простого утверждения. Следующий уровень — соединение отрицаемого утверждения с «Яблоки — это фрукты». Утверждение, что «яблоки — это фрукты, а груши — нет» неверно, поэтому буква «F» идет под точкой.
B ⊃ (А ∙ ~ П) т Т F FT Этот оператор с точкой является следствием условного, а антецедент условного оператора истинен, поэтому само условие ложно; буква «F» идет под подковой.Я покрасила его в красный цвет, чтобы было заметнее.
B ⊃ (А ∙ ~ П) т F Т F FT Теперь, здесь, в Drupal, единственный способ выровнять эти символы прямо — это представить их в виде таблицы. Но таблица, показывающая нам, что B ⊃ (A ∙ ~ P) ложна, не является тем, что мы называем «таблицей истинности».Таблица истинности показывает все возможные значения истинности, которые простые утверждения в составе или наборе составных частей могут иметь , и показывает нам результат этих значений. Пример, который мы рассматриваем, вычисляет значение одного составного оператора, не демонстрируя всех возможностей, которые допускает форма этого оператора.
Таблицы, которые мы использовали для определения операторов, повторенные ниже, являются таблицами истинности. Для этих утверждений нет комбинаций значений истинности, которые не были показаны.
Отрицание
Соединение
п. ∙ q т Т Т т F F Ф F Т Ф F F Дизъюнкция
п. v q т Т Т т Т F Ф Т Т Ф F F Условный материал
п. ⊃ q т Т Т т F F Ф Т Т Ф Т F Двусторонняя
п. ≡ q т Т Т т F F Ф F Т Ф Т F Таблицы истинности предоставляют функциональное определение истинности пяти операторов.С помощью этих определений мы можем вычислить значение истинности составных утверждений, если мы узнаем значения истинности простых утверждений, из которых они состоят. Вот несколько примеров и несколько упражнений, в которых вы можете практиковаться. Используйте свои обширные знания, чтобы начать с присвоения подходящих значений истинности простым утверждениям.
Ньют будет выступать в Мэри Вашингтон и в Университете Свободы.
Каждое из этих простых утверждений истинно, поэтому составленная из них конъюнкция (M ∙ L) также верна.
Если Либерти и Мэри Вашингтон оба приглашают Ньюта, а Либерти — евангелический университет, то Мэри Вашингтон тоже должна быть.
Это условное выражение имеет антецедент, и это соединение само по себе является союзом:
((Д ∙ М) ∙ Э) ⊃ Ш
L = Свобода приглашает Тритона
M = Мэри Вашингтон приглашает Ньют
E = Свобода евангельская
W = Мэри Вашингтон — евангелистка.
((Д ∙ М) ∙ Э) ⊃ Вт
((L ∙ М) ∙ E) ⊃ Вт т Т Т Т Т F F Я закодировал значения истинности цветом: первое, что мы можем ввести, это зеленый, потому что L ∙ M — наименьшая единица; второй — синий, который объединяет значение L ∙ M со значением E.Последний — красный, который берет истинный антецедент и ложный следствие, давая ложное условное утверждение. (Надеюсь, вы не думали, что это аргумент, а не утверждение.) Кстати, не делайте вывод из этого примера, что первое значение, которое вы можете вычислить, всегда будет крайним левым. Последнее значение, которое вы можете указать, — это значение, называемое главным оператором: это выражение является условным, его основным оператором является подкова.
Вот еще несколько, с которыми вы можете попрактиковаться:
1.Обама и Хиллари — демократы, если Ньют — республиканец.
2. Либо Обама будет баллотироваться, либо Ньют — демократ.
3. Если Клинтон баллотируется, то ей не менее 35 лет.
4. Обама является главнокомандующим тогда и только тогда, когда он является президентом.
5. Родиться в Америке — необходимое условие для того, чтобы стать президентом.
6. Если рождение здесь является необходимым условием для бега, Губернатор не может работать.
7. Либо Юм не изобретал таблицы истинности, либо, если Витгенштейн написал Трактат, тогда парадокс Рассела был плохой новостью для Фреге; однако Кант отрицал, что «существование» было предикатом тогда и только тогда, когда аристотелевская логика доминировала в течение двух тысяч лет.
Вот это весело. Давайте поэкспериментируем с этим (как только вы определите истинность простых утверждений)
(Юм не изобретал таблицы истинности, это сделал Витгенштейн, и он тоже написал Трактат. Парадокс Рассела был очень плохой новостью для Фреге (и не только для него!). Именно Канту мы обязаны проницательностью, чтобы не рассматривать » существование »как предикат, и, конечно же, логика Аристотеля доминировала в западной философии в течение двух тысяч лет — до тех пор, пока современная символическая логика не была разработана такими людьми, как Фреге, Рассел и Витгенштейн.)
8. Если либо Юм не изобретал таблицы истинности, либо Витгенштейн написал Трактат, тогда парадокс Рассела был плохой новостью для Фреге; но Кант отрицал, что «существование» было предикатом только в том случае, если аристотелевская логика доминировала в течение двух тысяч лет.
9. Либо Юм не изобретал таблицы истинности, либо Витгенштейн написал Трактат, и парадокс Рассела был плохой новостью для Фреге только в том случае, если Кант отрицал, что «существование» было предикатом, учитывая, что логика Аристотеля господствовала в течение двух тысяч лет.
10. Если неверно и то, что Юм изобрел таблицы истинности, и то, что Кант отрицал, что «существование» было предикатом, то, учитывая, что логика Аристотеля доминировала в течение двух тысяч лет, то, что Витгенштейн писал «Трактат», подразумевает, что парадокс Рассела был плохой новостью для Фреге.
Итак, это единственное, что мы делаем, применяя таблицы истинности: вычисляет значения истинности составных утверждений , учитывая, что мы знаем значения истинности простых утверждений, из которых они составлены.
Другое применение таблиц истинности позволяет нам классифицировать каждое функциональное утверждение истинности как попадающее в одну из трех категорий. Как вы могли заметить, значения истинности простых утверждений в 8-10 не изменились, но значения истинности основных операторов изменились. Это потому, что они представляют собой виды утверждений, в которых значения истинности утверждений имеют значение и определяют значение истинности соединения с учетом значений операторов. Такое утверждение называется «условным», что в данном контексте означает, что ценность целого зависит (контингентна) от стоимости частей.(Существует еще один философский смысл «случайности» экзистенциальной природы, который не имеет ничего общего с этим логическим представлением о ней.)
Но есть также утверждения, которые имеют свою истинностную ценность как следствие своей структуры, а не как следствие их содержания. Некоторые утверждения верны, потому что их структура делает их истинными, и не имеет значения, о Витгенштейне, Леонардо или Шалтай-Болтая. Их называют «тавтологиями». И затем есть третья группа, ложные из-за своей структуры, которые, опять же, не могут быть ничем иным, как ложными, независимо от того, какой контент вы им даете.Это называется «внутренними противоречиями».
Вот простой пример внутреннего противоречия: «Я думаю, что ты прав, но я думаю, что ты ошибаешься». Форма этого — R ∙ ~ R. Интуитивно понятно, что в этом утверждении что-то не так, т.е. что оно ложно.
Как ясно из этой таблицы, всегда будет F под точкой в соединении, которое соединяет утверждение с его собственным отрицанием.
Вот тавтология:
Каждый класс является либо членом самого себя, либо нет.
Мы могли бы записать это как M v ~ M.
Каждое утверждение, не связанное с его отрицанием, будет истинным. «Либо утверждение истинно, либо ложно» — тоже тавтология (поскольку «ложь» и «неправда» — синонимы).
Я представил это на очень простых примерах, но вот еще несколько сложных случаев, над которыми вы можете поработать, потренироваться в расчетах и привыкнуть классифицировать утверждения на случайности, тавтологии и внутренние противоречия:
Прежде чем вы сможете это сделать, вам нужно освежить в памяти, сколько строк требуется для таблицы истинности.Формула: «Количество строк = 2 в n-й степени», где «n» — количество простых утверждений. Это означает, что если есть только один простой оператор, нужны только две строки (одна строка показывает, что происходит, когда она истинна, другая показывает, что происходит, когда она ложна). Итак, для №1 ниже требуется всего две строки. Для оператора с двумя простыми операторами требуется 4, для одного с тремя — 8, для одного с четырьмя — 16, для одного с пятью — 32, для одного с шестью — 64.
1. M ⊃ (M ⊃ M)
2.(G ⊃ G) ⊃ G
3. (S ⊃ R) ∙ (S ∙ ~ R)
4. [(Q ⊃ P) ∙ (~ Q ⊃ R)] ∙ ~ (P v R)
5. {[(G ∙ N) ⊃ H] ∙ [(G ⊃ H) ⊃ P]} ⊃ (N ⊃ P)
Помимо составления таблиц истинности для них, убедитесь, что вы можете выразить их словами: например, 1 и 2 не говорят одно и то же, но что они говорят? 1 говорит: «M означает, что M влечет M.» (Его также можно прочитать как «Если M истинно, то M подразумевает M.» Или как «Если M, то если M, то M.» Что говорит 2?
Переведите это и сделайте таблицу.
Платежный баланс уменьшится тогда и только тогда, когда процентные ставки останутся стабильными; однако это не тот случай, когда процентные ставки не останутся стабильными или платежный баланс снизится.
Теперь, когда вы знаете, как вычислять значения и как строить таблицы истинности, вы можете применить это к другой задаче, а именно к сравнить операторы с другими операторами . Когда у вас есть набор составных и / или простых утверждений, вы можете составить таблицу, которая показывает все возможности их истинностных значений, и судить по ней, эквивалентны ли какие-либо два или более из них друг другу (например, тройной bar и biconditional), или противоречат ли они друг другу (что не то же самое, что утверждение, противоречащее самому ), или согласованы ли они или несовместимы друг с другом.Эти характеристики могут быть считаны из таблицы истинности механически. Если два или более утверждений всегда имеют одно и то же значение истинности под своими основными операторами, они эквивалентны. Если они имеют противоположные значения под своими основными операторами, они противоречат друг другу (как A и O в категориальной логике). Если они никогда не показывают истину в одной строке, они несовместимы (то есть, они не могут быть оба истинными) , и если они показывают истину хотя бы в одной строке под своим основным оператором, они согласованы друг с другом (что означает, что при определенных случайных обстоятельствах они оба могут быть правдой).
Вот несколько примеров, на которых вы можете это попробовать. Для каждой пары утверждений составьте таблицу истинности для каждого из выражений, а затем сравните их построчно в соответствии с их основными операторами. Посмотрите, что вы найдете.
1. ~ (p ∙ q) и ~ p ∙ ~ q
2. F ∙ M и ~ (F v M)
3. ~ A ≡ X и (X ∙ ~ A) v (A ∙ ~ X)
4. Q ⊃ ~ (K v F) и (K ∙ Q) v (F ∙ Q)
5.из Краткого введения в логику Херли:
Кристина и Томас обсуждают свои планы на вечер. Кристина: «Если ты меня не любишь, то я точно не буду заниматься с тобой сексом». Томас: «Ну, это означает, что если я тебя люблю, ты займешься со мной сексом, верно?» Томас прав? (Подсказка: составьте таблицу истинности для каждого утверждения и сравните их.)
Еще одна подсказка: в следующий раз, когда в романтическом разговоре будет неловкая тишина, предложите составить таблицы истинности!
6.Семантика логики высказываний — логика и доказательство 3.18.4 документация
Классически мы думаем о пропозициональных переменных как о диапазоне утверждений, которые могут быть истинными или ложными. И интуитивно мы думаем о системе доказательств, как о том, какие пропозициональные формулы должны быть истинными, чтобы были истинными, независимо от того, что означают переменные. Например, тот факт, что мы можем доказать \ (C \) из гипотез \ (A \), \ (B \) и \ (A \ wedge B \ to C \), кажется, говорит нам, что всякий раз, когда гипотезы true, то \ (C \) также должно быть истинным.
Чтобы понять это, нужно выйти за пределы системы и дать отчет об истинности — точнее, условиях, при которых пропозициональная формула истинна. Это одна из вещей, для которой была разработана символическая логика, и эта задача относится к области семантики . Формулы и формальные доказательства — это синтаксических понятий, то есть они представлены символами и символическими структурами. Истина — это семантическое понятие в том смысле, что оно приписывает тип , означающий , определенным формулам.
Синтаксически мы могли задавать следующие вопросы и отвечать на них:
Учитывая набор гипотез \ (\ Gamma \) и формулу \ (A \), можем ли мы вывести \ (A \) из \ (\ Gamma \)?
Какие формулы можно получить из \ (\ Gamma \)?
Какие гипотезы необходимы для вывода \ (A \)?
Вопросы, которые мы рассматриваем семантически разные:
Учитывая присвоение значений истинности пропозициональным переменным, встречающимся в формуле \ (A \), является ли \ (A \) истинным или ложным?
Есть ли какое-либо присвоение истинности, которое делает \ (A \) истинным?
Какие определения истинности делают \ (A \) истинным?
В этой главе мы не будем предоставлять полностью строгую математическую обработку синтаксиса и семантики.Этот предмет подходит для более продвинутого и целенаправленного курса математической логики. Но мы обсудим семантические вопросы достаточно подробно, чтобы дать вам хорошее представление о том, что означает семантическое мышление, а также о том, как прагматично использовать семантические понятия.
6.1. Истинные ценности и присвоения
Первое понятие, которое нам понадобится, — это значение истинности . Мы уже видели два, а именно «истинное» и «ложное». Мы будем использовать символы \ (\ mathbf {T} \) и \ (\ mathbf {F} \), чтобы представить их в неформальной математике.Это значения, которые \ (\ top \) и \ (\ bot \) предназначены для обозначения при естественном вычитании, а
trueиfalseпредназначены для обозначения в Lean.В этом тексте мы примем «классическое» понятие истины, следуя нашему обсуждению в разделе 5. Это можно понимать по-разному, но, в частности, все сводится к следующему: мы будем предполагать, что любое утверждение либо истинно. или ложь (но, конечно, не оба сразу). Эта концепция истины лежит в основе закона исключенного третьего, \ (A \ vee \ neg A \).Семантически мы читаем это предложение как «либо \ (A \) истинно, либо \ (\ neg A \) истинно». Поскольку в нашей семантической интерпретации \ (\ neg A \) истинно именно тогда, когда \ (A \) ложно, закон исключенной середины говорит, что \ (A \) либо истинно, либо ложно.
Следующее понятие, которое нам понадобится, — это присвоение истинности , которое представляет собой просто функцию, которая присваивает значение истинности каждому элементу набора пропозициональных переменных. В этом разделе мы будем различать пропозициональные переменные и произвольные формулы, используя буквы \ (P, Q, R, \ ldots \) для первых и \ (A, B, C, \ ldots \) для вторых.Например, функция \ (v \), определенная в
\ (v (P): = \ mathbf {T} \)
\ (v (Q): = \ mathbf {F} \)
\ (v (R): = \ mathbf {F} \)
\ (v (S): = \ mathbf {T} \)
— это задание истинности для набора переменных \ (\ {P, Q, R, S \} \).
Интуитивно задание истинности описывает возможное «состояние мира». Возвращаясь к загадке «Злоба и Алиса», предположим, что следующие буквы являются сокращениями для утверждений:
\ (P \): = Брат Алисы стал жертвой
\ (Q \): = Алиса была убийцей
\ (R \): = Алиса была в баре
В мире, описанном решением головоломки, первое и третье утверждения верны, а второе — ложно.Таким образом, наше присвоение истинности дает значение \ (\ mathbf {T} \) \ (P \) и \ (R \), а значение \ (\ mathbf {F} \) — \ (Q \).
Как только у нас есть присвоение истинности \ (v \) набору пропозициональных переменных, мы можем расширить его до функции оценки \ (\ bar v \), которая присваивает значение истина или ложь каждой пропозициональной формуле, которая зависит только от этих переменных. Функция \ (\ bar v \) определяется рекурсивно, то есть формулы вычисляются снизу вверх, так что значение, присвоенное составной формуле, определяется значениями, присвоенными ее компонентам.Формально функция определяется следующим образом:
\ (\ bar v (\ top) = \ mathbf {T} \).
\ (\ bar v (\ bot) = \ mathbf {F} \).
\ (\ bar v (\ ell) = v (\ ell) \), где \ (\ ell \) — любая пропозициональная переменная.
\ (\ bar v (\ neg A) = \ mathbf {T} \), если \ (\ bar v (A) \) равно \ (\ mathbf {F} \), и наоборот.
\ (\ bar v (A \ wedge B) = \ mathbf {T} \), если \ (\ bar v (A) \) и \ (\ bar v (B) \) оба являются \ (\ mathbf { T} \) и \ (\ mathbf {F} \) в противном случае.
\ (\ bar v (A \ vee B) = \ mathbf {T} \), если хотя бы одно из \ (\ bar v (A) \) и \ (\ bar v (B) \) равно \ ( \ mathbf {T} \); в противном случае \ (\ mathbf {F} \).
\ (\ bar v (A \ to B) = \ mathbf {T} \), если \ (\ bar v (B) \) равно \ (\ mathbf {T} \) или \ (\ bar v ( A) \) равно \ (\ mathbf {F} \), и \ (\ mathbf {F} \) в противном случае. (Эквивалентно \ (\ bar v (A \ to B) = \ mathbf {F} \), если \ (\ bar v (A) \) равно \ (\ mathbf {T} \) и \ (\ bar v ( B) \) равно \ (\ mathbf {F} \), и \ (\ mathbf {T} \) в противном случае.)
Правила конъюнкции и дизъюнкции легко понять.«\ (A \) и \ (B \)» истинно именно тогда, когда \ (A \) и \ (B \) оба истинны; «\ (A \) или \ (B \)» истинно, если истинно хотя бы одно из \ (A \) или \ (B \).
Сложнее понять правило импликации. Люди часто удивляются, узнав, что любое утверждение «если-то» с ложной гипотезой должно быть истинным. Утверждение «если у меня две головы, то круги есть квадраты» может звучать так, как будто оно должно быть ложным, но, по нашим подсчетам, оно оказывается верным. Чтобы понять это, подумайте о разнице между двумя предложениями:
«Если у меня две головы, то круги будут квадратами.”
«Если бы у меня было две головы, то круги были бы квадратами».
Второе предложение — это пример контрфактического следствия . Он утверждает что-то о том, как мир мог бы измениться, если бы все было иначе, чем есть на самом деле. Философы веками изучали контрфакты, но математическая логика имеет дело с первым предложением, подразумевая материальный смысл . Материальный подтекст говорит о том, каков мир сейчас, а не о том, каким он мог бы быть.Поскольку неверно, что у меня две головы, утверждение «если у меня две головы, то круги являются квадратами».
Почему мы так оцениваем материальные последствия? И снова давайте рассмотрим истинное предложение: «каждое простое натуральное число больше двух нечетно». Мы можем интерпретировать это предложение как утверждение, что все (бесконечно много) предложений в этом списке верны:
Если 0 простое и больше 2, то 0 нечетное.
Если 1 простое и больше 2, то 1 нечетное.
Если 2 простое и больше 2, то 2 нечетное.
Если 3 простое и больше 2, то 3 нечетное.
…
Первое предложение в этом списке очень похоже на наш пример с «двумя головами», поскольку и гипотеза, и заключение ложны. Но поскольку это экземпляр утверждения, которое в целом истинно, мы обязуемся присвоить ему значение \ (\ mathbf {T} \). Второе предложение иное: гипотеза все еще ложна, но здесь вывод верен.Вместе они говорят нам, что всякий раз, когда гипотеза ложна, условное утверждение должно быть истинным. Четвертое предложение содержит верную гипотезу и верный вывод. Итак, из второго и четвертого предложений мы видим, что всякий раз, когда вывод является истинным, условное выражение также должно быть истинным. Наконец, кажется очевидным, что предложение «если 3 простое и больше 2, то 3 четное» должно быть истинным , а не . Этот паттерн, в котором гипотеза верна, а вывод ложен, является единственным, для которого условие будет ложным.
Давайте мотивируем семантику материальной импликации другим способом, используя дедуктивные правила, описанные в предыдущей главе. Обратите внимание, что если \ (B \) истинно, мы можем доказать \ (A \ to B \) без каких-либо предположений относительно \ (A \):
Это следует из правильного прочтения правила введения импликации: учитывая \ (B \), всегда можно вывести \ (A \ to B \), а затем отменить предположение \ (A \), , если оно есть . Если \ (A \) никогда не использовался в доказательстве, вывод просто слабее, чем должен быть.Этот вывод подтвержден в Lean:
.переменных A B: Prop переменная hB: B пример: A → B: = Предположим, что hA: A, показать B, от hBАналогично, если \ (A \) ложно, мы можем доказать \ (A \ to B \) без каких-либо предположений относительно \ (B \):
В Lean:
переменных A B: Prop переменная hnA: ¬ A пример: A → B: = Предположим, что hA: A, показать B, из false.elim (hnA hA)Наконец, если \ (A \) истинно, а \ (B \) ложно, мы можем доказать \ (\ neg (A \ to B) \):
Еще раз, в Lean:
переменных A B: Prop переменная hA: A переменная hnB: ¬B пример: ¬ (A → B): = Предположим, что h: A → B, иметь hB: B, от h hA, показать ложь, от hnB hBТеперь, когда мы определили истинность любой формулы относительно присвоения истинности, мы можем ответить на наш первый семантический вопрос: дано присвоение \ (v \) значений истинности пропозициональным переменным, присутствующим в некоторой формуле \ (\ varphi \) , как определить, истинно ли \ (\ varphi \)? Это равносильно вычислению \ (\ bar v (\ varphi) \), а рекурсивное определение \ (\ varphi \) дает рецепт: мы оцениваем выражения, встречающиеся в \ (\ varphi \) снизу вверх, начиная с пропозициональные переменные и использование оценки компонентов выражения для оценки самого выражения.Например, предположим, что наше присвоение истинности \ (v \) делает \ (A \) и \ (B \) истинными, а \ (C \) ложными. Чтобы оценить \ ((B \ to C) \ vee (A \ wedge B) \) под \ (v \), обратите внимание, что выражение \ (B \ to C \) оказывается ложным, а выражение \ (A \ wedge B \) оказывается верным. Поскольку дизъюнкция «ложь или истина» истинна, вся формула истинна.
Мы также можем пойти в другом направлении: имея формулу, мы можем попытаться найти определение истинности, которое сделает ее истинной (или ложной). Фактически, мы можем использовать Lean для оценки формул за нас.В следующем примере вы можете присвоить любой набор значений символам предложения
A,B,C,DиE. Когда вы запускаете Lean на этом входе, вывод оператораevalявляется значением выражения.- Определите здесь свое назначение правды def A: = tt def B: = ff def C: = tt def D: = tt def E: = ff def test (p: Prop) [разрешимый p]: string: = если p, то «истина» иначе «ложь» #eval test ((A ∧ B) ∨ ¬ C) #eval test (A → D) #eval test (C → (D ∨ ¬E)) #eval test (¬ (A ∧ B ∧ C ∧ D))Попробуйте варьировать назначения истины, чтобы увидеть, что произойдет.Вы можете добавить свои собственные формулы в конец ввода и также оценить их. Постарайтесь найти такие определения истинности, которые сделают каждую из проверенных выше формул истинной. В качестве дополнительной задачи попробуйте найти одно задание истинности, которое сделает их все одновременно истинными.
6.2. Таблицы истинности
Второй и третий вопросы по семантике, которые мы задали, немного сложнее первого. Для данной формулы \ (A \) существует ли какое-либо присвоение истинности, которое делает \ (A \) истинным? Если да, то какие присвоения истинности делают \ (A \) истинным? Вместо того, чтобы рассматривать одно конкретное назначение истинности, эти вопросы просят нас количественно оценить более всех возможных назначений истины.n \) возможные присвоения истинности. Это число очень быстро растет, поэтому здесь мы в основном рассмотрим более мелкие формулы.
Мы воспользуемся так называемой таблицей истинности , чтобы выяснить, когда формула верна, если вообще верна. В левой части таблицы истинности мы поместим все возможные назначения истинности для настоящих пропозициональных букв. В правой части мы поместим значение истинности всей формулы под соответствующее присвоение.
Начнем с того, что таблицы истинности можно использовать для краткого описания семантики наших логических связок:
Мы предоставим вам составить таблицу для \ (\ neg A \) в качестве легкого упражнения.
Для составных формул стиль почти такой же. Иногда может быть полезно включить промежуточные столбцы со значениями истинности подформул:
Записывая таблицу истинности для формулы, мы можем взглянуть на строки и увидеть, какие назначения истинности делают формулу истинной. Если все записи в последнем столбце — \ (\ mathbf {T} \), как в приведенном выше примере, формула считается действительной .
6.3. Обоснованность и полнота
Предположим, мы имеем в виду фиксированную систему дедукции, такую как естественная дедукция.Пропозициональная формула называется доказуемой , если есть формальное доказательство ее в этой системе. Говорят, что пропозициональная формула является тавтологией или действительной , если она истинна при любом назначении истинности. Доказуемость — это синтаксическое понятие, поскольку оно утверждает существование синтаксического объекта, а именно доказательства. Валидность — это семантическое понятие, поскольку оно связано с присвоением истинности и оценками. Но интуитивно эти понятия должны совпадать: оба выражают идею, что формула \ (A \) имеет , чтобы быть истинным, или обязательно , чтобы быть истинным, и можно было бы ожидать, что хорошая система доказательств позволит нам вывести действительную формулы.
Утверждение, что каждая доказуемая формула действительна, известно как обоснованность . Если \ (A \) — любая формула, логики используют обозначение \ (\ vdash A \), чтобы выразить доказуемость \ (A \), и обозначение \ (\ vDash A \), чтобы выразить это \ (A \ ) является действительным. (Первый символ иногда называют «турникетом», а второй символ иногда называют «двойным турникетом».) При таком обозначении разумность говорит о том, что для каждой пропозициональной формулы \ (A \), если \ (\ vdash A \ ), затем \ (\ vDash A \).Обратное, которое гласит, что каждая действительная формула доказуема, называется полнотой . В символических терминах это говорит, что для каждой формулы \ (A \), если \ (\ vDash A \), то \ (\ vdash A \).
Из-за того, как мы выбрали наши правила вывода и определили понятие оценки, эта интуиция о том, что эти два понятия должны совпадать, остается верной. Другими словами, система естественного вывода, которую мы представили для логики высказываний, является надежной и полной в отношении семантики таблицы истинности.
Эти понятия разумности и полноты распространяются на доказуемость гипотез. Если \ (\ Gamma \) — это набор пропозициональных формул и \ (A \) — пропозициональная формула, то \ (A \) называется логическим следствием из \ (\ Gamma \), если для любого присвоение истинности, которое делает каждую формулу в \ (\ Gamma \) истинной, \ (A \) также истинно. В этом расширенном контексте разумность говорит, что если \ (A \) доказуемо из \ (\ Gamma \), то \ (A \) является логическим следствием \ (\ Gamma \). Полнота идет другим путем: если \ (A \) является логическим следствием \ (\ Gamma \), это доказуемо из \ (\ Gamma \).В символических терминах мы пишем \ (\ Gamma \ vdash A \), чтобы выразить, что \ (A \) доказуемо по формулам из \ (\ Gamma \) (или что \ (\ Gamma \) доказывает \ (A \)), и мы пишем \ (\ Gamma \ vDash A \), чтобы выразить, что \ (A \) является логическим следствием \ (\ Gamma \) (или что \ (\ Gamma \) влечет за собой \ (A \)). С этой записью, разумность говорит, что для каждой пропозициональной формулы \ (A \) и набора пропозициональных формул \ (\ Gamma \), если \ (\ Gamma \ vdash A \), то \ (\ Gamma \ vDash A \), и полнота говорит, что для любых \ (A \) и \ (\ Gamma \), если \ (\ Gamma \ vDash A \), то \ (\ Gamma \ vdash A \).
Учитывая набор пропозициональных формул \ (\ Gamma \) и пропозициональную формулу \ (A \), предыдущий раздел дает нам рецепт решения, влечет ли \ (\ Gamma \) за \ (A \): построить таблицы истинности для всех формул в \ (\ Gamma \) и \ (A \), и проверьте, истинно ли каждое \ (A \) в каждой строке таблицы, в которой верна каждая формула \ (\ Gamma \). (Неважно, что происходит с \ (A \) в строках, где некоторая формула в \ (\ Gamma \) ложна.)
Обратите внимание, что с помощью правил естественного вывода формула \ (A \) доказуема на основе набора гипотез \ (\ {B_1, B_2, \ ldots, B_n \} \) тогда и только тогда, когда формула \ (B_1 \ клин B_2 \ клин \ cdots \ клин B_n \ to A \) доказывается напрямую, то есть без гипотез.Таким образом, по крайней мере для конечных наборов формул \ (\ Gamma \) два утверждения о правильности и полноте эквивалентны.
Доказательство достоверности и полноты относится к области метатеории , поскольку оно требует от нас размышлений о наших методах рассуждения. Это не является центральной темой этой книги: мы больше озабочены , используя логику и понятие истины, чем установление их свойств. Но понятия разумности и полноты играют важную роль, помогая нам понять природу логических понятий, и поэтому мы попытаемся дать здесь некоторые подсказки относительно того, почему эти свойства верны для логики высказываний.
Доказать правильность проще, чем полноту. Мы хотим показать, что всякий раз, когда \ (A \) доказуемо с помощью набора гипотез \ (\ Gamma \), то \ (A \) является логическим следствием \ (\ Gamma \). В следующей главе мы рассмотрим доказательства по индукции, которая позволяет нам установить свойство, выполняемое для общего набора объектов, показывая, что оно выполняется для некоторых «простых» и сохраняется при переходе к более сложным объектам. В случае естественной дедукции достаточно показать, что надежность имеет место в самых основных доказательствах — с использованием правила предположения — и что она сохраняется при каждом правиле вывода.Базовый случай прост: правило предположения гласит, что \ (A \) доказуемо на основе гипотезы \ (A \), и ясно, что каждое присвоение истинности, которое делает \ (A \) истинным, делает \ (A \) истинным. Индуктивные шаги не намного сложнее; они включают проверку того, что выбранные нами правила связаны с семантическими понятиями. Например, предположим, что последнее правило — это правило и-введения. В этом случае у нас есть доказательство \ (A \) из некоторых гипотез \ (\ Gamma \) и доказательство \ (B \) из некоторых гипотез \ (\ Delta \), и мы объединяем их, чтобы сформировать доказательство \ (A \ wedge B \) из гипотез в \ (\ Gamma \ cup \ Delta \), то есть гипотез в обоих.Индуктивно, мы можем предположить, что \ (A \) является логическим следствием \ (\ Gamma \) и что \ (B \) является логическим следствием \ (\ Delta \). Пусть \ (v \) будет любым назначением истинности, которое делает каждую формулу в \ (\ Gamma \ cup \ Delta \) истинной. Тогда по индуктивному предположению мы имеем, что оно делает истинным \ (A \), а также \ (B \). По определению функции оценки \ (\ bar v (A \ wedge B) = \ mathbf {T} \), как требуется.
Доказать полноту сложнее. Достаточно показать, что если \ (A \) — любая тавтология, то \ (A \) доказуема.Одна из стратегий — показать, что естественная дедукция может моделировать метод таблиц истинности. Например, предположим, что \ (A \) состоит из пропозициональных переменных \ (B \) и \ (C \). Тогда при естественном дедукции мы сможем доказать
\ [(B \ клин C) \ vee (B \ клин \ neg C) \ vee (\ neg B \ клин C) \ vee (\ neg B \ клин \ neg C), \]
с одним дизъюнктом для каждой строки таблицы истинности. Затем мы должны иметь возможность использовать каждый дизъюнкт для «оценки» каждого выражения, встречающегося в \ (A \), доказывая его истинность или ложность в соответствии с его оценкой, пока у нас не будет доказательства самого \ (A \).
Более приятный способ продолжить — это выразить правила естественного вывода таким образом, чтобы мы могли работать в обратном направлении от \ (A \) в поисках доказательства. Другими словами, сначала мы даем процедуру построения вывода \ (A \), работая в обратном направлении от \ (A \). Затем мы утверждаем, что если процедура терпит неудачу, то в той точке, где она терпит неудачу, мы можем найти определение истинности, которое делает \ (A \) ложным. В результате, если каждое присвоение истинности делает \ (A \) истинным, процедура возвращает доказательство \ (A \).
6.4. Упражнения
.
Покажите, что \ (A \ to B \), \ (\ neg A \ vee B \) и \ (\ neg (A \ wedge \ neg B) \) логически эквивалентны, выписав таблицу истинности и показывая, что они имеют одинаковые значения для всех назначений истины.
Запишите таблицу истинности для \ ((A \ to B) \ wedge (B \ wedge C \ to A) \).
Покажите, что \ (A \ to B \) и \ (\ neg B \ to \ neg A \) эквивалентны, выписав таблицы истинности и показывая, что они имеют одинаковые значения для всех назначений истинности.
Имеет ли место следующее влечение?
\ [\ {A \ to B \ vee C, \ neg B \ to \ neg C \} \ models A \ to B \]
Обоснуйте свой ответ, выписав таблицу истинности (извините, она длинная). Четко укажите строки, в которых обе гипотезы верны.
Можно ли вывести следующие формулы? Обоснуйте свой ответ либо выводом, либо контрпримером.
\ (\ neg (\ neg A \ vee B) \ to A \)
\ ((\ neg A \ to \ neg B) \ to (A \ to B) \)
\ (((P \ клин Q) \ to R) \ to (R \ vee \ neg P) \)
\ ((\ neg P \ wedge \ neg Q) \ to \ neg (Q \ vee P) \)
