Таблица истинности дизъюнкция: 404 | Университет СИНЕРГИЯ — RC74 — интернет-магазин радиоуправляемых моделей

Содержание

Логические операции — урок. Информатика, 8 класс.

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

Конъюнкция (логическое умножение) — логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.

Для записи конъюнкции используются следующие знаки: И,ˆ,⋅,&.

Например: A И B,AˆB,A⋅B,A&B.

Конъюнкцию можно описать в виде таблицы, которую называют таблицей истинности:

В таблице истинности перечисляются все возможные значения исходных высказываний (столбцы $A$ и $B$), причём соответствующие им двоичные числа, как правило, располагают в порядке возрастания: $00, 01, 10, 11$. В последнем столбце записан результат выполнения логической операции для соответствующих операндов.

Пример:

$A$ = «Джордж Буль создал новую область науки — математическую логику»,

$B$ = «Клод Шеннон связал математическую логику с работой компьютера».

Построим сложное высказывание A И B: «Джордж Буль создал новую область науки — математическую логику, и Клод Шеннон связал математическую логику с работой компьютера» истинно только в том случае, когда одновременно истинны оба исходных высказывания.

Дизъюнкция

Рассмотрим два высказывания:

$A$ = «Идея использования в логике математической символики принадлежит Готфриду Вильгельму Лейбницу»,

$B$ = «Лейбниц является основоположником бинарной арифметики».

Очевидно, новое высказывание «Идея использования в логике математической символики принадлежит Готфриду Вильгельму Лейбницу или Лейбниц является основоположником бинарной арифметики» ложно только в том случае, когда одновременно ложны оба исходных высказывания.

Дизъюнкция — логическая операция, которая каждым двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.

Для записи дизъюнкции используются следующие знаки: ИЛИ;∨;|;+.

Например: A ИЛИ B;A∨B;A|B;A+B.

Дизъюнкция определяется следующей таблицей истинности:

Обрати внимание!

Дизъюнкцию также называют логическим сложением.

Инверсия

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

Для записи инверсии используются следующие знаки: НЕ;¬;−

Например: НЕ А;¬А;А−.
Инверсия определяется следующей таблицей истинности:

Обрати внимание!

Инверсию также называют логическим отрицанием.

Отрицанием высказывания «У меня дома есть компьютер» будет высказывание «Неверно, что у меня дома есть компьютер» или, что в русском языке то же самое, что «У меня дома нет компьютера».

Отрицанием высказывания «Я не знаю китайский язык» будет высказывание «Неверно, что я не знаю китайский язык» или, что в русском языке: «Я знаю китайский язык».

Отрицанием высказывания «Все юноши $8-х$ классов — отличники» является высказывание «Неверно, что все юноши $8-х$ классов — отличники», другими словами, «Не все юноши $8-х$ классов — отличники».

Таким образом, при построении отрицания к простому высказыванию либо используется речевой оборот «неверно, что …», либо отрицание строится к сказуемому, тогда к соответствующему глаголу добавляется частица «не».

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

Последовательность выполнения логических операций:

Инверсия;
Конъюнкция;
Дизъюнкция.

Если в выражении присутствуют скобки, то приоритет операций меняется, сначала выполняются действия в скобках.

Основы логики, логические операции и таблицы истинности

Конъюнкция

«Конъюнкция» это одна из логических операций наряду с дизъюнкцией, инверсией, импликацией и эквивалентности. Иначе её называют логической «И». В программировании её обозначают чаще всего как «and» или «&» Считается истинным только в одном случае, когда оба операнда (оба сравниваемых элемента, если по простому) являются истинными (true, 1). В остальных же случаях, где какой либо из операндов ложный, или ложны оба, значения выражения будет ложно.

Для наглядности смотрите таблицу:

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

конъюнкция

«A«	«B«	«A» и «B»
1	1	1
1	0	0
0	1	0
0	0	0

Таблица истинности Конъюнкция

Конъюнкция

может быть бинарной, то есть иметь всего два операнда (как например «A» «B») тернарной («A» «B» «C») или вообще иметь сколько угодно операндов, ( в этом случае она будет называться N-арной операцией) где n любое число.

Обозначения

Как я уже писал выше обозначения Конъюнкции встречаются совершенно разные приведу примеры:

a ⋀ b, a & b, a and b, a * b , ab в последнем варианте знак умножения точка может быть пропущен как и в обычном умножении. Как например в записи формулы используется запись подряд 7a + 2b где умножение между семеркой и «a» нету. Чаще всего используют запись «перевернутой галочки», ⋀ где она больше всего распространена в математике.

Дизъюнкция

Дизъюнкция — логическая операция которая обозначает логическое сложение. можно обозначить как «ИЛИ» потому что этот союз максимально похоже отражает суть дизъюнкции. Или этот операнд или тот, или сразу оба.

Также как и конъюкция это логическое выражение может быть двоичной или сколько угодно n- арной.

Считается истиной в почти во всех случаях кроме как два операнда ложных (False, 0)

Таблица истинности для дизъюнкции

A	B	«A» или «B»
1	1	1
1	0	1
0	1	1
0	0	0

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

Дизъюнкция

Обозначения

Дизъюнкцию чаще всего записывают как

a ⋁ b, a || b, a | b, a OR b, обратите пожалуйста внимание что в первом случае это не буква V, а другой знак «галочка вниз» которая обозначает дизъюнкцию

Инверсия

С инверсией всё достаточно просто, оно преобразует операнд в обратный ему. Например если изначально у нас было ложное высказывание, то оно станет истинным, а истинное же с инверсией станет ложным.

Обозначение

Обозначается оно обычно ¬, или записывается как «НЕ»

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

Инверсия

Таблица истинности инверсия

Абсолютно ничего сложного.

Давайте теперь рассмотрим следующую логическую операцию:

Импликация

Таблица импликация

A	B	«A» → «B»
1	1	1
1	0	0
0	1	1
0	0	1

Таблица истинности импликация

Обозначение

Обознается обычно знаком стрелочка →

Эквивалентность

Таблица

Эквивалентность

A	B	«A» ‘B»
1	1	1
1	0	0
0	1	0
0	0	1

Таблица истинности Эквивалентность

Обозначение

обычно обозначается символом ≡ или ↔

отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция, законы де Моргана, тавтология, таблицы истинности

п.1. Отрицание

Отрицанием высказывания A называется новое высказывание «не A», принимающее значение «истина», если A ложно, и значение «ложь», если A истинно.

Обозначение отрицания $\overline{A}$ читается «не A».
Если записать эту операцию с помощью таблицы истинности, где 0 обозначает «ложь», а 1 – «истина», получаем:

Закон отрицания отрицания. Двойное отрицание $\overline{\overline{A}}=A$ истинно только в том случае, если истинно исходное высказывание

Правило отрицания высказываний с кванторами: $$ \mathrm{ \overline{(\forall x)A(x)}=(\exists x)\overline{A(x)},\ \ \overline{(\exists x)A(x)}=(\forall x)\overline{A(x)} } $$

Расшифровка первого правила: высказывание «неверно, что для любого x выполняется A(x)» совпадает с высказыванием «найдётся x, для которого A(x) не выполняется».
Расшифровка второго правила: высказывание «неверно, что найдётся x, для которого выполняется A(x)» совпадает с высказыванием «для любого x A(x) не выполняется».2-1\geq 0} & \\ \mathrm{x\gt\frac12} & \end{array}\right. \Leftrightarrow x\leq -1 \cup x\gt\frac12 $$

п.4. Импликация

Импликация двух высказываний – это высказывание, которое будет ложным, если первое высказывание истинно, а второе ложно; а во всех остальных случаях – будет истинным.

Обозначение импликации A → B, читается «если A, то B».
Высказывание A называют «посылкой», а высказывание B – «заключением».
Значение импликации зависит от порядка высказываний.
Таблица истинности:

п.5. Эквиваленция

Эквиваленция двух высказываний – это высказывание, которое будет истинным только при совпадении истинности обоих высказываний; а при несовпадении – будет ложным.

Обозначение эквиваленции A ↔ B, читается «A то же самое, что

B» или «A эквивалентно B».
Таблица истинности:

п.6. Законы де Моргана

Отрицание конъюнкции эквивалентно дизъюнкции отрицаний: $\mathrm{\overline{A\wedge B}=\overline{A}\vee\overline{B}}$

Докажем эквивалентность с помощью таблиц истинности:

A ∧ B

$\mathrm{\overline{A\wedge B}}$

$\mathrm{\overline{A}}$

$\mathrm{\overline{B}}$

$\mathrm{\overline{A}\vee\overline{B}}$

Мы видим, что итоговые столбцы слева и справа полностью совпадают.

Значит, высказывания эквивалентны.

Отрицание дизъюнкции эквивалентно конъюнкции отрицаний: $\mathrm{\overline{A\vee B}=\overline{A}\wedge\overline{B}}$

Докажем эквивалентность с помощью таблиц истинности:

A ∨ B

$\mathrm{\overline{A\vee B}}$

$\mathrm{\overline{A}}$

$\mathrm{\overline{B}}$

$\mathrm{\overline{A}\wedge\overline{B}}$

Высказывания слева и справа эквивалентны.

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

Внимание!

Не путайте эквиваленцию и эквивалентность.
Эквиваленция – это логическая операция с 0 или 1 на выходе, в зависимости от исходных А и В.
Эквивалентность(равносильность) – это отношение, при котором эквиваленция A ↔ B истинна при всех значениях логических переменных на области определения. Тогда A ⇔ B (пишут также A=B, A≡B, A~B).
Если A ⇔ B, то каждое из предложений является и необходимым и достаточным условием для другого предложения; используются словосочетания «необходимо и достаточно», «равносильно».

п.7. Алгоритм доказательства эквивалентности высказываний с помощью таблиц истинности

На входе: две формулы алгебры высказываний, соединенные отношением эквивалентности «=».
Шаг 1. Построить таблицу истинности для формулы слева от знака «=».

Шаг 2. Построить таблицу истинности для формулы справа от знака «=».
Шаг 3. Сравнить итоговые столбцы двух таблиц. Если столбцы полностью совпадают, формулы эквивалентны.

Например:
Докажем следующее свойство:

Отрицание импликации эквивалентно конъюнкции посылки и отрицания заключения: $$ \mathrm{ \overline{A\rightarrow B}=A \wedge\overline{B} } $$

A → B

$\mathrm{\overline{A\rightarrow B}}$

$\mathrm{\overline{B}}$

$\mathrm{A\wedge\overline{B}}$

Столбцы совпадают. Значит, формулы эквивалентны.
Что и требовалось доказать.

п.8. Тавтология

Тавтологией (или законом логики) называется формула, принимающая значение истины при любых значениях переменных.

Таблица истинности для тавтологии даёт итоговый столбец, заполненный только единицами.

Например: $\mathrm{A \vee \overline{A}}$

$\mathrm{\overline{A}}$

$\mathrm{A\vee\overline{A}}$

«Быть иль не быть» — это тавтология.

п.9. Примеры

Пример 1. Для формулы P(x, y)=(∃x∀y)(A(x,y)∧B(x,y))
сформулируйте предложения A и B, при которых:

а) формула всегда истинна; б) формула всегда ложна.

a) A(x,y): квадрат числа x больше y
B(x,y): куб числа x больше y
Пусть x = |y + 1|. Тогда x² = (y + 1)² > y – истинно ∀y
x³ = |y + 1|³ > y – ∀y
Таким образом, мы нашли x, при котором A(x,y) ∧ B(x,y) = 1 для любого y, т.е.
P(x,y) = 1.

б) A(x,y): x больше y
B(x,y): x меньше y
A(x,y)∧B(x,y) = 0 – ложно для любого y, т.к. не существует x, который одновременно был бы больше и меньше y.
P(x,y) = 0.

Пример 2. Составьте таблицу истинности для формулы $P=(\overline{A}\rightarrow B)\vee (A\rightarrow \overline{B})$.
Является ли данная формула тавтологией?

$\mathrm{\overline{A}}$

$\mathrm{\overline{B}}$

$\mathrm{\overline{A}\rightarrow B}$

$\mathrm{A\rightarrow \overline{B}}$

Это – тавтология.

Пример 3*. Составьте таблицу истинности для формулы
P = (A → B) ∧ (B → C) → (A → C)
Является ли данная формула тавтологией?

A → B

B → C

A → C

(A → B)
∧
(B → C)

Это – тавтология.

Основы логики. Логические операции и таблицы истинности

Логические операции и таблицы истинности

1) Логическое умножение или конъюнкция:

Конъюнкция — это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.
Обозначение: F = A & B; F = A и B; F = A and B; F = A /\ B

Таблица истинности для конъюнкции

A	B	F
1	1	1
1	0	0
0	1	0
0	0	0

2) Логическое сложение или дизъюнкция:

Дизъюнкция — это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.
Обозначение: F = A + B; F = A или B; F = A or B; F = A V B

Таблица истинности для дизъюнкции

A	B	F
1	1	1
1	0	1
0	1	1
0	0	0

3) Логическое отрицание или инверсия:

Инверсия — это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

Таблица истинности для инверсии

4) Логическое следование или импликация:

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

Таблица истинности для импликации

A	B	F
1	1	1
1	0	0
0	1	1
0	0	1

5) Логическая равнозначность или эквивалентность:

Эквивалентность — это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

Таблица истинности для эквивалентности

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

Порядок выполнения логических операций в сложном логическом выражении

1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.

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

Редактировалось Дата: Понедельник, 06 Сентябрь 2021

Таблица истинности которая считывает функцию Python

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

import re

class BoolVar:
    def __init__(self, value):
        self.value = value
        #print("INIT =", value)

    # '-' — возражения "нет"
    def __neg__(self):
        return BoolVar(not self.value)

    # '+' — дизъюнкция "или"
    def __add__(self, other):
        return BoolVar(self.value or other.value)

    # '*' — конъюнкция "и"
    def __mul__(self, other):
        return BoolVar(self.value and other.value)

    # '>' — импликация "если ..., тогда"
    def __gt__(self, other):
        return BoolVar((not self.value) or other.value)

    # '=' — эквивалентность "ровно"
    def __eq__(self, other):
        return BoolVar(self.value == other.value)
    
    # строковое представление значения
    def __str__(self):
        return "True" if self.value else "False"

    def __format__(self, format_spec):
        return format(str(self), format_spec)

infunc = input('Enter your function: ')
# в питоне знак эквивалентности - это '==', так что заменяем
infunc = infunc.replace("=", "==")
# находим переменные в функции, т.е. просто буквы
# set() делает этот набор уникальным, ну и сортируем
variables = sorted(set(re.findall(r"[A-Za-z]", infunc)))
# или так, если надо без использования регулярных выражений
# variables = sorted(set([c for c in infunc if c.isalpha()]))

# просто красивое оформление для таблицы
header = [""]*2
for key in variables:
    header[0] += "-"*7 + "+"
    header[1] += f"   {key}   |"
header[0] += "-+" + "-"*7
header[1] += " | Result"
print("\n".join(header + header[0:1]))
    
vars_for_eval = {}
# вариантов входных значений для таблицы - 2 в степени кол-ва переменных
for variant in range(1 << len(variables)):
    # заполняем входной словарь c представлением переменных 
    # в виде экземпляров нашего класса для функции eval()
    # key идут в прямом порядке, а i - в обратном
    for i, key in reversed(list(enumerate(reversed(variables)))):
        # используем биты этого числа для инициализыции булевых значений 
        vars_for_eval[key] = BoolVar(variant & (1 << i))
        # вывод строки таблицы истинности
        print(f" {vars_for_eval[key]:<5}", end=" |")
    # вычисляем результат
    result = eval(infunc, {}, vars_for_eval)
    print(f" | {result:<5}")

print(header[0])

Оно даже чего-то считает:

D:\Programming\Python\1>python bools.py
Enter your function: a+b
-------+-------+-+-------
   a   |   b   | | Result
-------+-------+-+-------
 False | False | | False
 False | True  | | True
 True  | False | | True
 True  | True  | | True
-------+-------+-+-------

D:\Programming\Python\1>python bools.py
Enter your function: -x=y
-------+-------+-+-------
   x   |   y   | | Result
-------+-------+-+-------
 False | False | | False
 False | True  | | True
 True  | False | | True
 True  | True  | | False
-------+-------+-+-------

D:\Programming\Python\1>python bools.py
Enter your function: -p+(p*q)=q
-------+-------+-+-------
   p   |   q   | | Result
-------+-------+-+-------
 False | False | | False
 False | True  | | True
 True  | False | | True
 True  | True  | | True
-------+-------+-+-------

Кстати, программу заодно можно использовать как калькулятор. 🙂

D:\Programming\Python\1>python bools.py
Enter your function: 55*23-16**5//16
-+-------
 | Result
-+-------
 | -64271
-+-------

Построение таблиц истинности

Цель урока: Повторить высказывание и логические операции. Закрепить навыки работы с логическими операциями- конъюнкция, дизъюнкция, инверсия.

Тип урока: комбинированный урок (КУ)

Формы работы учащихся: индивидуальная, работа в парах, фронтальная работа.

Просмотр содержимого документа
«Построение таблиц истинности»

САМОПОДГОТОВКА:

Для всех:

п.1.3.2-1.3.3

стр.24-30,

по учеб. №8, стр.39

Р.т. № 81

Индивид. : № 11

Написать, что такое:

конъюнкция,
дизъюнкция,
инверсия,

обозначения, таблицы истинности для данных операций.

Опорный конспект

Высказывание – это предложение на любом языке, содержание которого

можно однозначно определить как истинное или ложное.

Основные логические

операции

Дизъюнкция

Конъюнкция

Инверсия

A & B

A V B

Приоритет выполнения логических операций: ¬, &, V .

Рабочая тетрадь:

№ 76, 77, 79, 80

Тема:

Построение таблиц истинности.

ЗАПОЛНИТЕ ТАБЛИЦУ ИСТИННОСТИ

ФОРМУЛА

ВЫСКАЗЫ

ВАНИЕ

Зверь полосатый

ТИГР

ВОЛК

Зверь хищный

не А

БУРУНДУК

не В

ЗАЯЦ

А и В

А или В

ПРОВЕРИМ!

ФОРМУЛА

ВЫСКАЗЫ

ВАНИЕ

Зверь полосатый

ТИГР

Зверь хищный

не А

ВОЛК

Зверь не полосатый

не В

БУРУНДУК

Зверь не хищный

А и В

ЗАЯЦ

Зверь полосатый и хищный

А или В

Зверь полосатый или хищный

Построение таблиц истинности для логических выражений

подсчитать n — число переменных в выражении

подсчитать общее число логических операций в выражении

установить последовательность выполнения логических операций

определить число столбцов в таблице

заполнить шапку таблицы, включив в неё переменные и операции

определить число строк в таблице без шапки: m =2 n

Записать все возможные значения переменных

провести заполнение таблицы по столбцам, выполняя логические

операции в соответствии с установленной последовательностью

Физминутка:

Пример построения таблицы истинности

А V A & B

n = 2, m = 2 2 = 4 .

Приоритет операций: &, V

A&B

A V A&B

Закрепление :

СОСТАВИТЬ ТАБЛИЦУ ИСТИННОСТИ

F = (A v B) & (A v B)

AvB

СОСТАВИТЬ ТАБЛИЦУ ИСТИННОСТИ

F = (A v B) & (A v B)

AvB

Рефлексия

Был ли полезен урок?

Был ли интересен урок?

Оцените работу класса.

Оцените свою работу.

Составные предложения | Практическая информатика

Для построения составных предложений чаще всего используются связки — И (&&, конъюнкция) и ИЛИ (||, дизъюнкция). Смысл связки И — тот же, что и в разговорной речи: конъюнкция двух предложений истинна тогда и только тогда, когда они оба истинны. Связка ИЛИ «двойственна» связке И: дизъюнкция двух предложений ложна только если они оба ложны.

Дизъюнкция нескольких предложений ложна тогда, когда все они ложны. Рассмотрим, например, утверждение «Плата за подписку снижена для студентов, лиц моложе 21 года и безработных». Согласно ему, приходится платить полную цену, только если все три исключения нарушены. Аналогичное обобщение верно и для связки И. Конъюнкция нескольких предложений истинна, только если все они истинны.

Кроме И и ИЛИ, имеется еще модификатор НЕ (!, отрицание) результат применения которого противоположен его аргументу: !T = F, !F = T. В математической литературе для обозначения отрицания выражения проводят горизонтальную черту над ним.

Значения логических выражений, содержащих связки И, ИЛИ и модификатор НЕ, вычисляются с помощью так называемой таблицы истинности:

A	B	A && B	A \|\| B	! A
T	T	T	T	F
T	F	F	T	F
F	T	F	T	T
F	F	F	F	T

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

Пример

Вычислить значение логической формулы !X && Y || X && Z

при следующих значениях переменных: X = F, Y = T, Z = T.

Решение

Отметим цифрами порядок выполнения операций:

1 	 	2 	 	4 	 	3 	 
! 	X 	&& 	Y 	|| 	X 	&& 	Z

Используя таблицу истинности, вычислим формулу по шагам:

1) !F = T; 	2) T && T = T;
3) F && T = F; 	4) T || F = T.

Итак, формула при данных значениях аргументов принимает значение T.

Задание

Определите значение логического выражения !(X>Z) && !(X=Y), если:

1) X = 3, Y = 5, Z = 2;
2) X = 0, Y = 1, Z = 19;

Таблицы истинности — отрицание, соединение, дизъюнкция («не», «и», «или»)

Таблицы истинности — это способ анализа того, как обоснованность утверждений (называемых пропозициями) ведет себя, когда вы используете логическое «или» или логическое «и» для их объединения. Утверждения либо полностью верны, либо полностью ложны, поэтому любая таблица истинности захочет показать обе эти возможности для всех сделанных утверждений.

Для всех этих примеров мы будем обозначать p и q предложениями.Это могут быть утверждения типа «Мне 25 лет» или «Сейчас теплее 70 °». Любые утверждения, которые являются правдой или ложью.

Отрицание — «не р»

Отрицание — это утверждение «не p», обозначаемое \ (\ neg p \), и поэтому оно будет иметь значение истинности, противоположное p. Если p истинно, то \ (\ neg p \), если ложно. Если p ложно, то \ (\ neg p \) истинно. Обратите внимание, что таблица истинности показывает все эти возможности.

Соединение — «и»

Рассмотрим утверждение «p и q», обозначенное \ (p \ wedge q \).Чтобы проанализировать это, мы сначала должны подумать обо всех комбинациях значений истинности для обоих утверждений, а затем решить, как эти комбинации влияют на утверждение «и». Прописью:

Строка 1 : оба утверждения могут быть верными.
В этом случае имело бы смысл, что «p и q» также являются истинным утверждением.
Строка 2 : p может быть ложным, а q — истинным.
Для того, чтобы «p и q» были истинными, нам нужно, чтобы были истинными ОБА утверждения. Поскольку один из них ложен, «p и q» ложны.
Строка 3 : p может быть истинным, а q — ложным.
Если это так, то по тому же аргументу в строке 2 «p и q» ложны.
Строка 4 : оба утверждения могут быть ложными.
Если оба утверждения ложны, тогда «p и q» ложны.

Порядок строк не имеет значения — пока мы систематичны таким образом, чтобы не пропустить никаких возможных комбинаций значений истинности для двух исходных утверждений p, q.

Дизъюнкция — «или»

Вы можете этого не осознавать, но есть два типа «или».Есть включительно или , где мы допускаем тот факт, что оба утверждения могут быть правдой, и есть исключительная или , где мы строго следим за тем, чтобы истинным было только одно или другое утверждение. В математике «или», с которым мы работаем, является включающим или, обозначаемым \ (p \ vee q \). Когда мы хотим работать с эксклюзивным или, мы конкретны и используем другую нотацию (вы можете прочитать об этом здесь: эксклюзивное или). Это показано в первой строке таблицы истинности, которую мы сейчас проанализируем:

Строка 1 : оба утверждения могут быть верными.
Поскольку мы работаем с включающим или, утверждение «p или q» в этом случае будет истинным.
Строка 2 : p может быть ложным, а q — истинным.
В этом суть или. Мы говорим «одно или оба утверждения верны». Следовательно, в данном случае верно «p или q».
Строка 3 : p может быть истинным, а q — ложным.
То же, что и второй ряд.
Строка 4 : оба утверждения могут быть ложными.
Принимая во внимание значение или, если оба утверждения ложны, тогда неверно, что «p или q», поэтому мы перечисляем ложные для этого утверждения.

Сводка

Чтобы отслеживать, как работают эти идеи, запомните следующее:

«не p» всегда имеет значение истинности, противоположное p
«p и q» верны только тогда, когда оба утверждения верны (в противном случае — ложь)
«p или q» неверно, только если оба утверждения ложны (в противном случае — истина)

Понимание этих таблиц истинности позволит нам позже анализировать сложные составные композиции, состоящие из и, или, не, и, возможно, даже условного оператора, поэтому убедитесь, что у вас есть эти основы!

объявление

Продолжить рассмотрение отдельных математических тем

Далее: Таблицы истинности для условных и двусмысленных (подразумевает и если и только)

Подпишитесь на нашу рассылку новостей!

Мы всегда публикуем новые бесплатные уроки и добавляем новые учебные пособия, руководства по калькуляторам и пакеты задач.

Подпишитесь, чтобы получать электронные письма (раз в пару или три недели) с информацией о новинках!

Связанные

% PDF-1.5 % 2 0 obj > / Метаданные 5 0 R / StructTreeRoot 6 0 R >> эндобдж 5 0 obj > транслировать 2017-09-07T07: 54: 05-04: 002017-09-07T07: 54: 16-04: 00Microsoft® Word 2013Microsoft® Word 2013application / pdf конечный поток эндобдж 22 0 объект > транслировать xkoF ~ 澹! r ^ m ^} i? (HD ꏼ} | i !, ٙ a.P2n? o RU 鮾 =? {3ɦdphYAdf2eFDu_l {~ fWDҮfB> Ωg | e_ | XFx `sJ d? j: S> njzxfJTN> nZ ڟ 0 xs7ec? w C @ bqB: @ 1C2H) * d.x ف G, ‘uG! lͳ 😕 ] -MnyD

Краткое содержание главы

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

В логике высказываний мы используем символы для обозначения отношений между утверждениями, то есть для обозначения формы аргумента.Эти отношения становятся возможными благодаря логическим связкам, таким как союз (и), дизъюнкция (или), отрицание (не) и условное (если … то …). Связки используются в составных операторах, каждый из которых состоит как минимум из двух простых операторов. Утверждение — это предложение, которое может быть либо истинным, либо ложным.
Чтобы указать возможные значения истинности утверждений и аргументов, мы можем построить таблицы истинности, графический способ отображения всех возможных значений истинности.
Конъюнкция ложна, если хотя бы один из ее компонентов утверждения (конъюнктов) ложен. Дизъюнкция остается верной, даже если одно из ее составных утверждений (дизъюнктов) ложно. Отрицание — это отрицание утверждения. Отрицание любого утверждения изменяет значение истинности утверждения на его противоречивое (ложное на истинное и истинное на ложное). Условное утверждение ложно только в одной ситуации — когда антецедент истинен, а следствие ложно.
Использование таблиц истинности для определения действительности аргумента основано на том факте, что у действительного аргумента не может быть истинных посылок и ложного заключения.Базовая таблица истинности состоит из двух или более столбцов-указателей, в которых перечислены все варианты значений истинности, за которыми следуют столбцы для каждой посылки и заключения. Мы можем добавить другие столбцы, чтобы помочь нам определить значения истинности компонентов аргумента.
Вы можете проверить правильность аргументов не только с помощью таблиц истинности, но и с помощью короткого метода. В этой процедуре мы пытаемся обнаружить, есть ли способ сделать вывод ложным, а посылки истинными, путем присвоения различных значений истинности компонентам аргумента.

Atomic Statement — обзор

15.4 Установление требований

Системные требования для этого примера были предоставлены заинтересованной стороной в форме постановки задачи, описанной на рисунке 15.1. Постановка проблемы отражена в диаграмме требований на рисунке 15.6. Заголовок диаграммы указывает, что фрейм представляет собой пакет с названием Distiller Requirements .

Рисунок 15.6. Диаграмма требований с требованиями дистиллятора верхнего уровня из постановки задачи.

Исходное заявление о требованиях обозначено идентификатором требования S0.0 . На этой диаграмме показаны отношения сдерживания: как требование S0.0 разлагается на отдельные атомарные требования с S.1 по S.5 . Декомпозиция требований указывает, что ничего не было добавлено или вычтено из утверждений в исходном требовании S.0 , но составной оператор был заменен набором элементарных операторов, каждое из которых можно индивидуально проанализировать и проверить.

Часто возникает необходимость вывести более явные требования из существующего набора требований. Например, требование S1.0 гласит: « Система должна очищать грязную воду. ”Здесь не сказано, что система должна кипятить воду, но что она должна очищать воду. Чтобы четко понять, что система должна очищать воду путем ее кипячения, мы должны вывести новое требование, а именно: требование S2.0 утверждает, что система должна « Нагревать грязную воду… », а требование S3.0 гласит, что система должна « Кипятить грязную воду…. ”Просто необходимо показать производные отношения между очищением, нагреванием и кипячением. Это дает обоснование для вывода требования D1.0 .

Требование S2.0 гласит, что « Нагрев грязной воды и конденсированный пар осуществляется с помощью противоточного теплообменника. ”Требования могут быть взяты из S2.0 , в котором указано « Система должна содержать противоточный теплообменник » и « Система должна нагревать грязную воду » и « Система должна конденсировать пар ». Следует также отметить, что эти утверждения были предоставлены как требования, но они навязывают проектное решение. Обычно нежелательно иметь требования, чрезмерно ограничивающие пространство для решения; однако это может не входить в компетенцию разработчика системы. Системный инженер несет ответственность за установление диалога с заказчиком и сортировку истинных требований от предположений о решении.

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

Может показаться удивительным видеть свойства воды, отслеживаемые как требования, которые отображаются на диаграмме требований. Смысл этого состоит в том, чтобы иметь полную прослеживаемость от постановки проблемы клиента до проекта. Если бы свойства воды каким-либо образом были оценены как неправильные, их документирование таким образом дало бы обоснование того, почему они были изменены, или, по крайней мере, обеспечило бы диалог с заказчиком, чтобы помочь в процессе проверки требований.

В этом примере все исходные требования, как исходные, так и разложенные, начинаются с S .Все производные требования начинаются с D . Ожидается, что проект устанавливает соглашение о нумерации требований, и что инструменты могут помочь в обеспечении соблюдения этого соглашения. Номера требований могут соответствовать номерам конкретных параграфов в спецификации.

Рисунок 15.7 включает требования в табличном формате, который является допустимой нотацией в SysML. Это традиционный способ просмотра требований. Таблица на рисунке представляет собой отчет по модели и содержит часть той же информации, что и на диаграмме требований; он предоставляет идентификатор требования, имя и текст.В этом случае таблица полагается на нумерацию, чтобы указать иерархию или отношения включения, но это могло быть показано на уровне отступов или на другом механизме.

Рисунок 15.7. Таблица декомпозиции требований.

На рисунке 15.8 также показан табличный формат требований, но он включает отношения между требованиями. В дополнение к идентификатору и имени в таблице фиксируется производное отношение, которое показывает, как одно требование является производным от другого, а также обоснование этой связи.Когда необходимо следовать нескольким отношениям, создается дерево требований. Эта информация также отображается в графическом виде на диаграмме требований, которая является полезным способом ввода взаимосвязей; однако часто бывает более компактно просматривать информацию в табличном формате. Ожидается, что инструменты предоставят табличный формат для требований и других типов информации о моделировании, как описано в главе 4.

Рисунок 15.8. Трассировка требований в табличном формате.

Обратите внимание, что в Приложении C спецификации OMG SysML перечислены ненормативные типы требований, которые могут использоваться.Пользователи могут захотеть использовать эти типы и / или создать определяемые пользователем расширения, используя механизм профилей, описанный в главе 14.

Propositional Logic

Раздел 3.1 Логика высказываний

Расследовать!

Вы наткнулись на двух троллей, играющих в Stratego®. Вам говорят:

Тролль 1: Если мы кузены, то мы оба лжецы.
Тролль 2: Мы кузены или оба лжецы.

Могли ли оба тролля быть рыцарями? Вспомните, что все тролли либо всегда говорят правду рыцарей, либо всегда лгут.

Предложение — это просто утверждение. Логика высказываний изучает способы взаимодействия утверждений друг с другом. Важно помнить, что логика высказываний на самом деле не заботится о содержании утверждений. Например, с точки зрения логики высказываний утверждения «если луна сделана из сыра, то баскетбольные мячи — круглые» и «если у пауков восемь ног, то Сэм ходит прихрамывая». Они оба импликации: утверждения формы \ (P \ imp Q \ text {.} \)

Подраздел Таблицы истинности

Вот вопрос об игре в Монополию:

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

Верно или неверно? Мы ответим на этот вопрос, и нам не нужно будет ничего знать о «Монополии». Вместо этого мы рассмотрим логическую форму заявления .

Нам нужно решить, когда утверждение \ ((P \ imp Q) \ vee (Q \ imp R) \) истинно.Используя определения связок в разделе 0.2, мы видим, что для того, чтобы это было правдой, либо \ (P \ imp Q \) должно быть истинным, либо \ (Q \ imp R \) должно быть истинным (или и то, и другое). Они истинны, если либо \ (P \) ложно, либо \ (Q \) истинно (в первом случае) и \ (Q \) ложно, либо \ (R \) истинно (во втором случае). Так что… да, становится немного запутанно. К счастью, мы можем составить диаграмму, чтобы отслеживать все возможности. Введите таблиц истинности . Идея такова: в каждой строке мы перечисляем возможные комбинации T и F (для истинного и ложного) для каждой из сентенциальных переменных, а затем отмечаем, является ли рассматриваемое утверждение истинным или ложным в этом случае.Мы делаем это для всех возможных комбинаций T и F. Тогда мы сможем ясно увидеть, в каких случаях утверждение истинно или ложно. Для сложных операторов мы сначала введем значения для каждой части оператора, чтобы разделить нашу задачу на более мелкие и более управляемые части.

Поскольку значение истинности утверждения полностью определяется значениями истинности его частей и тем, как они связаны, все, что вам действительно нужно знать, — это таблицы истинности для каждой логической связки.Вот они:

\ (П \)	\ (Q \)	\ (P \ клин Q \)
т	Т	Т
т	Ф	Ф
Ф	Т	Ф
Ф	Ф	Ф

\ (П \)	\ (Q \)	\ (P \ vee Q \)
т	Т	Т
т	Ф	Т
Ф	Т	Т
Ф	Ф	Ф

\ (П \)	\ (Q \)	\ (П \ имп Q \)
т	Т	Т
т	Ф	Ф
Ф	Т	Т
Ф	Ф	Т

\ (П \)	\ (Q \)	\ (P \ iff Q \)
т	Т	Т
т	Ф	Ф
Ф	Т	Ф
Ф	Ф	Т

Таблица истинности отрицания выглядит так:

Ни одна из этих таблиц истинности не должна вызывать удивления; все они просто повторяют определения связок.Попробуем еще один.

Пример 3.1.1.

Составьте таблицу истинности для утверждения \ (\ neg P \ vee Q \ text {.} \)

Решение

Обратите внимание, что это утверждение не является \ (\ neg (P \ vee Q) \ text {,} \), отрицание принадлежит только \ (P \). Вот таблица истинности:

\ (П \)	\ (Q \)	\ (\ neg P \)	\ (\ neg P \ vee Q \)
т	Т	Ф	Т
т	Ф	Ф	Ф
Ф	Т	Т	Т
Ф	Ф	Т	Т

Мы добавили столбец для \ (\ neg P \), чтобы упростить заполнение последнего столбца.Записи в столбце \ (\ neg P \) определялись записями в столбце \ (P \). Затем, чтобы заполнить последний столбец, посмотрите только на столбец для \ (Q \) и столбец для \ (\ neg P \) и используйте правило для \ (\ vee \ text {.} \)

Теперь давайте ответим на наш вопрос о монополии:

Пример 3.1.2.

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

Решение

Представьте утверждение символами как \ ((P \ imp Q) \ vee (Q \ imp R) \ text {,} \), где \ (P \) — это утверждение «вы получаете больше дублей, чем любой другой игрок», \ (Q \) — это утверждение «вы потеряете», а \ (R \) — утверждение «вы, должно быть, купили больше всего собственности.«Теперь составьте таблицу истинности.

Таблица истинности должна содержать 8 строк, чтобы учесть все возможные комбинации истины и ложности среди трех утверждений. Вот полная таблица истинности:

\ (П \)	\ (Q \)	\ (R \)	\ (П \ имп Q \)	\ (Q \ имп R \)	\ ((П \ имп Q) \ vee (Q \ имп R) \)
т	Т	Т	Т	Т	Т
т	Т	Ф	Т	Ф	Т
т	Ф	Т	Ф	Т	Т
т	Ф	Ф	Ф	Т	Т
Ф	Т	Т	Т	Т	Т
Ф	Т	Ф	Т	Ф	Т
Ф	Ф	Т	Т	Т	Т
Ф	Ф	Ф	Т	Т	Т

Первые три столбца — это просто систематический список всех возможных комбинаций T и F для трех операторов (видите, как бы вы перечислили 16 возможных комбинаций для четырех операторов?).Следующие два столбца определяются значениями \ (P \ text {,} \) \ (Q \ text {,} \) и \ (R \) и определением импликации. Затем последний столбец определяется значениями в предыдущих двух столбцах и определением \ (\ vee \ text {.} \). Это последний столбец, о котором мы заботимся.

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

Утверждение о монополии является примером тавтологии , утверждения, которое истинно только на основании своей логической формы. Тавтологии всегда верны, но они мало что говорят нам о мире. Никаких знаний о монополии не требовалось, чтобы определить, что это утверждение верно. Фактически, в равной степени верно и то, что «Если луна сделана из сыра, тогда Элвис все еще жив, или если Элвис все еще жив, то у единорогов 5 ног».

Подраздел Логическая эквивалентность

Вы могли заметить в примере 3.1.1, что последний столбец в таблице истинности для \ (\ neg P \ vee Q \) идентичен последнему столбцу в таблице истинности для \ (P \ imp Q \ text {:} \)

\ (П \)	\ (Q \)	\ (П \ имп Q \)	\ (\ neg P \ vee Q \)
т	Т	Т	Т
т	Ф	Ф	Ф
Ф	Т	Т	Т
Ф	Ф	Т	Т

Это говорит о том, что независимо от того, что такое \ (P \) и \ (Q \), утверждения \ (\ neg P \ vee Q \) и \ (P \ imp Q \) либо оба истинны, либо оба ложны.Поэтому мы говорим, что эти утверждения логически эквивалентны .

Логическая эквивалентность.

Два (молекулярных) утверждения \ (P \) и \ (Q \) являются логически эквивалентными при условии, что \ (P \) истинно именно тогда, когда \ (Q \) истинно. То есть \ (P \) и \ (Q \) имеют одинаковое значение истинности при любом присвоении значений истинности их атомарным частям.

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

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

Пример 3.1.3.

Являются ли утверждения «не будет дождя и снега» и «не будет дождя и не будет снега» логически эквивалентными?

Решение

Мы хотим знать, является ли \ (\ neg (P \ vee Q) \) логически эквивалентным \ (\ neg P \ wedge \ neg Q \ text {.} \) Составьте таблицу истинности, которая включает оба утверждения:

\ (П \)	\ (Q \)	\ (\ neg (P \ vee Q) \)	\ (\ neg P \ клин \ neg Q \)
т	Т	Ф	Ф
т	Ф	Ф	Ф
Ф	Т	Ф	Ф
Ф	Ф	Т	Т

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

Обратите внимание, что этот пример дает нам способ «распределить» отрицание по дизъюнкции («или»). У нас есть аналогичное правило для распределения по союзу («и»):

Законы Де Моргана.

\ begin {уравнение *} \ neg (P \ wedge Q) \ text {логически эквивалентно} \ neg P \ vee \ neg Q \ text {.} \ end {уравнение *}

\ begin {уравнение *} \ neg (P \ vee Q) \ text {логически эквивалентно} \ neg P \ wedge \ neg Q \ text {.} \ end {уравнение *}

Это говорит о том, что может существовать своего рода «алгебра», которую вы могли бы применить к операторам (да, она есть: она называется булевой алгеброй ) для преобразования одного оператора в другой.Мы можем начать собирать полезные примеры логической эквивалентности и последовательно применять их к утверждению, вместо того, чтобы составлять сложную таблицу истинности.

Законы Де Моргана не помогают нам напрямую с последствиями, но, как мы видели выше, каждое значение может быть записано как дизъюнкция:

Последствия разъединения.

\ begin {уравнение *} P \ imp Q \ text {логически эквивалентно} \ neg P \ vee Q \ text {.} \ end {уравнение *}

Пример: «Если число кратно 4, то оно четное» эквивалентно «число не кратно 4 или (иначе) четно.

С этим и с законами Де Моргана вы можете взять любое утверждение и упростить до такой степени, что отрицания применяются только к атомарным предложениям. Ну, на самом деле нет, потому что вы можете сложить несколько отрицаний. Но с этим легко справиться:

Двойное отрицание.

\ begin {уравнение *} \ neg \ neg P \ text {логически эквивалентно} P \ text {.} \ end {уравнение *}

Пример: «Это не тот случай, когда \ (c \) не является нечетным» означает «\ (c \) нечетно.”

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

Пример 3.1.4.

Докажите, что утверждения \ (\ neg (P \ imp Q) \) и \ (P \ wedge \ neg Q \) логически эквивалентны без использования таблиц истинности.

Решение

Мы хотим начать с одного из операторов и преобразовать его в другое с помощью последовательности логически эквивалентных операторов. Начните с \ (\ neg (P \ imp Q) \ text {.} \) Мы можем переписать импликацию как дизъюнкцию, это логически эквивалентно

\ begin {уравнение *} \ Нег (\ Нег П \ Ви Q) \ текст {.} \ end {уравнение *}

Теперь примените закон ДеМоргана, чтобы получить

\ begin {уравнение *} \ neg \ neg P \ wedge \ neg Q \ text {.} \ end {уравнение *}

Наконец, используйте двойное отрицание, чтобы получить \ (P \ wedge \ neg Q \)

Обратите внимание, что приведенный выше пример показывает, что отрицание импликации НЕ является импликацией: это конъюнкция! Мы видели это раньше, в Разделе 0.2, но это настолько важно и полезно, что здесь стоит второй синий квадрат:

Отрицание следствия.

Отрицание импликации — это союз:

\ begin {уравнение *} \ neg (P \ imp Q) \ text {логически эквивалентно} P \ wedge \ neg Q \ text {.} \ end {уравнение *}

То есть, единственный способ, чтобы предположение было ложным, — это чтобы гипотеза была верной. И заключение было ложным.

Чтобы проверить, что два оператора логически эквивалентны, вы можете использовать таблицы истинности или последовательность логически эквивалентных замен. Метод таблицы истинности, хотя и громоздкий, имеет то преимущество, что он может проверить, что два оператора НЕ являются логически эквивалентными.

Пример 3.1.5.

Являются ли утверждения \ ((P \ vee Q) \ imp R \) и \ ((P \ imp R) \ vee (Q \ imp R) \) логически эквивалентными?

Решение

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

\ (П \)	\ (Q \)	\ (R \)	\ ((P \ vee Q) \ imp R \)	\ ((П \ имп R) \ vee (Q \ имп R) \)
т	Т	Т	Т	Т
т	Т	Ф	Ф	Ф
т	Ф	Т	Т	Т
т	Ф	Ф	Ф	Т
Ф	Т	Т	Т	Т
Ф	Т	Ф	Ф	Т
Ф	Ф	Т	Т	Т
Ф	Ф	Ф	Т	Т

Посмотрите на четвертый (или шестой) ряд.В этом случае \ ((P \ imp R) \ vee (Q \ imp R) \) истинно, но \ (((P \ vee Q) \ imp R \) ложно. Следовательно, эти утверждения не являются логически эквивалентными.

Хотя у нас нет логической эквивалентности, это случай, когда \ ((P \ vee Q) \ imp R \) истинно, так же как и \ ((P \ imp R) \ vee (Q \ imp R) \ text {.} \) Это говорит нам, что мы можем вывести \ ((P \ imp R) \ vee (Q \ imp R) \) из \ ((P \ vee Q) \ imp R \ text {, } \) только не в обратном направлении.

Подраздел Вычеты

Расследовать!

Холмс владеет двумя костюмами: черным и твидовым.Он всегда носит твидовый костюм или сандалии. Каждый раз, когда он надевает твидовый костюм и фиолетовую рубашку, он предпочитает не носить галстук. Он никогда не носит твидовый костюм, если он также не носит пурпурную рубашку или сандалии. Когда он носит сандалии, он также носит фиолетовую рубашку. Вчера Холмс надел галстук-бабочку. Что еще он носил?

Ранее мы утверждали, что следующий аргумент является допустимым:

Если Эдит съест свои овощи, то она может съесть печенье. Эдит съела свои овощи.Поэтому Эдит получает печенье.

Как мы узнаем, что это действительно так? Посмотрим на форму заявлений. Пусть \ (P \) означает «Эдит ест свои овощи», а \ (Q \) означает «Эдит может съесть печенье». Логическая форма аргумента:

	\ (П \ имп Q \)
	\ (П \)
\ (\ следовательно \)	\ (Q \)

Это пример правила вычета , форма аргумента, которая всегда действительна.Это особенно известное правило под названием modus ponens . Вы уверены, что это действительное правило вычета? Если нет, рассмотрите следующую таблицу истинности:

\ (П \)	\ (Q \)	\ (П \ имп Q \)
т	Т	Т
т	Ф	Ф
Ф	Т	Т
Ф	Ф	Т

Это просто таблица истинности для \ (P \ imp Q \ text {,} \), но здесь важно то, что все строки в правиле дедукции имеют свой собственный столбец в таблице истинности.Помните, что аргумент действителен при условии, что вывод должен быть верным, если предположения верны. Посылки в этом случае следующие: \ (P \ imp Q \) и \ (P \ text {.} \). Какие строк таблицы истинности соответствуют тому, что обе они истинны? \ (P \) истинно в первых двух строках, и из них только первая строка имеет истинное значение \ (P \ imp Q \). И, о чудо, в этом одном случае \ (Q \) также верно. Итак, если \ (P \ imp Q \) и \ (P \) оба истинны, мы видим, что \ (Q \) также должно быть истинным.

Вот еще несколько примеров.

Пример 3.1.6.

Покажите, что

	\ (П \ имп Q \)
	\ (\ neg P \ imp Q \)
\ (\ следовательно \)	\ (Q \)

— действительное правило вычета.

Решение

Мы составляем таблицу истинности, которая содержит все строки формы аргумента:

\ (П \)	\ (Q \)	\ (П \ имп Q \)	\ (\ neg P \)	\ (\ neg P \ imp Q \)
т	Т	Т	Ф	Т
т	Ф	Ф	Ф	Т
Ф	Т	Т	Т	Т
Ф	Ф	Т	Т	Ф

(мы включаем столбец для \ (\ neg P \) как шаг, чтобы помочь получить столбец для \ (\ neg P \ imp Q \)).

Теперь посмотрите на все строки, для которых истинны как \ (P \ imp Q \), так и \ (\ neg P \ imp Q \). Это происходит только в строках 1 и 3. Эй! В этих строках \ (Q \) также истинно, поэтому форма аргумента действительна (это действительное правило вывода).

Пример 3.1.7.

Решить, нужно ли

	\ (П \ имп R \)
	\ (Q \ имп R \)
	\ (R \)
\ (\ следовательно \)	\ (P \ vee Q \)

— действительное правило вычета.

Решение

Составим таблицу истинности, содержащую все четыре утверждения.

\ (П \)	\ (Q \)	\ (R \)	\ (П \ имп R \)	\ (Q \ имп R \)	\ (P \ vee Q \)
т	Т	Т	Т	Т	Т
т	Т	Ф	Ф	Ф	Т
т	Ф	Т	Т	Т	Т
т	Ф	Ф	Ф	Т	Т
Ф	Т	Т	Т	Т	Т
Ф	Т	Ф	Т	Ф	Т
Ф	Ф	Т	Т	Т	Ф
Ф	Ф	Ф	Т	Т	Ф

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

Пока перед нами таблица истинности, посмотрите на строки 1, 3 и 5. Это единственные строки, в которых все утверждения \ (P \ imp R \ text {,} \) \ (Q \ imp R \ text {,} \) и \ (P \ vee Q \) верны. Также бывает, что \ (R \) истинно и в этих строках. Таким образом, мы открыли новое правило вычета, которое, как мы знаем, является действительным :

	\ (П \ имп R \)
	\ (Q \ имп R \)
	\ (P \ vee Q \)
\ (\ следовательно \)	\ (R \)

Подраздел за пределами предложений

Как мы видели в разделе 0.2, не каждое утверждение можно проанализировать, используя только логические связки. Например, мы можем захотеть работать с оператором:

Все простые числа больше 2 нечетны.

Чтобы записать это утверждение символически, мы должны использовать кванторы. Можно перевести так:

\ begin {уравнение *} \ forall x ((P (x) \ wedge x \ gt 2) \ imp O (x)) \ text {.} \ end {уравнение *}

В этом случае мы используем \ (P (x) \) для обозначения «\ (x \) простое» и \ (O (x) \) для обозначения «\ (x \) нечетное.Это не предложения, поскольку их значение истинности зависит от ввода \ (x \ text {.} \). Лучше думать о \ (P \) и \ (O \) как об обозначении свойств их ввода. Технический термин для них — предикатов , и когда мы изучаем их логически, нам нужно использовать логику предикатов .

Важно подчеркнуть, что логика предикатов расширяет пропозициональную логику (во многом так же, как квантовая механика расширяет классическую механику). Вы заметите, что в нашем утверждении выше по-прежнему используются (пропозициональные) логические связки.Все, что мы узнали о логической эквивалентности и выводах, все еще применимо. Однако логика предикатов позволяет нам анализировать утверждения с более высоким разрешением, копаясь в отдельных предложениях \ (P \ text {,} \) \ (Q \ text {,} \) и т. Д.

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

Пример 3.1.8.

Предположим, мы утверждаем, что не существует наименьшего числа. Мы можем перевести это в символы как

\ begin {уравнение *} \ Neg \ существует x \ forall y (x \ le y) \ end {уравнение *}

(буквально: «неверно, что существует такое число \ (x \), что для всех чисел \ (y \ text {,} \) \ (x \) меньше или равно \ (y \) »).

Однако мы знаем, как отрицание взаимодействует с кванторами: мы можем передать отрицание квантору, переключив тип квантора (между универсальным и экзистенциальным).Таким образом, приведенное выше утверждение должно быть логически эквивалентным от до

\ begin {уравнение *} \ forall x \ существует y (y \ lt x) \ text {.} \ end {уравнение *}

Обратите внимание, что \ (y \ lt x \) является отрицанием \ (x \ le y \ text {.} \). Это буквально говорит: «Для каждого числа \ (x \) есть число \ (y \) который меньше, чем \ (x \ text {.} \) ». Мы видим, что это еще один способ сделать наше первоначальное утверждение.

Пример 3.1.9.

Можно ли изменить порядок квантификаторов? Например, рассмотрим два утверждения:

\ begin {уравнение *} \ forall x \ exists y P (x, y) \ qquad \ mathrm {и} \ qquad \ exists y \ forall x P (x, y) \ text {.} \ end {уравнение *}

Являются ли они логически эквивалентными?

Решение

Эти утверждения логически НЕ эквивалентны. Чтобы увидеть это, мы должны предоставить интерпретацию предиката \ (P (x, y) \), которая делает одно из утверждений истинным, а другое ложным.

Пусть \ (P (x, y) \) будет предикатом \ (x \ lt y \ text {.} \) Верно, что в натуральных числах для всех \ (x \) существует некоторое \ ( у \) больше, чем \ (х \) (поскольку чисел бесконечно много). Однако не существует натурального числа \ (y \), которое больше любого числа \ (x \ text {.} \) Таким образом, \ (\ forall x \ exists y P (x, y) \) может быть истинным, в то время как \ (\ exists y \ forall x P (x, y) \) ложно.

Однако мы не можем сделать обратное. Если существует некоторый \ (y \), для которого каждое \ (x \) удовлетворяет \ (P (x, y) \ text {,} \), то, безусловно, для каждого \ (x \) существует некоторый \ (y \) который удовлетворяет \ (P (x, y) \ text {.} \) Первый говорит, что мы можем найти один \ (y \), который работает для каждого \ (x \ text {.} \) Второй допускает разные \ ( y \) работают для разных \ (x \), но ничто не мешает нам использовать те же \ (y \), которые работают для каждого \ (x \ text {.} \) Другими словами, хотя у нас нет логической эквивалентности между двумя утверждениями, у нас есть действующее правило вывода:

	\ (\ существует y \ forall x P (x, y) \)
\ (\ следовательно \)	\ (\ forall x \ существует y P (x, y) \)

Другими словами, это означает, что единственный оператор

\ begin {уравнение *} \ существует y \ forall x P (x, y) \ imp \ forall x \ exists y P (x, y) \ end {уравнение *}

всегда верно.Это своего рода тавтология, хотя мы оставляем за собой этот термин для обозначения необходимых истин в логике высказываний. Утверждение логики предикатов, которое обязательно истинно, получает более престижное обозначение закона логики (или иногда логически действительного , но это менее забавно).

Упражнения Упражнения

1.

Рассмотрим высказывание о вечеринке: «Если у вас день рождения или будет торт, значит, будет торт».

Переведите приведенное выше утверждение в символы.Ясно укажите, какой оператор является \ (P \), а какой — \ (Q \ text {.} \)
Составьте таблицу истинности для утверждения.
Если предположить, что утверждение верно, что (если вообще что-либо) вы можете сделать вывод, будет ли торт?
Если предположить, что утверждение верно, то какой (если что-нибудь) вы можете сделать вывод, если торта не будет?
Предположим, вы узнали, что заявление было ложью. Какие выводы можно сделать?

Решение

\ (P \ text {:} \) это ваш день рождения; \ (Q \ text {:} \) будет торт.\ ((P \ vee Q) \ imp Q \)
Подсказка: вы должны получить три буквы Т и одну F.
Только то, что там будет торт.
Это НЕ твой день рождения!
Это твой день рождения, но торт — ложь.

2.

Составьте таблицу истинности для утверждения \ ((P \ vee Q) \ imp (P \ wedge Q) \ text {.} \)

Решение

\ (P \)	\ (Q \)	\ ((P \ vee Q) \ imp (P \ клин Q) \)
т	Т	Т
т	Ф	Ф
Ф	Т	Ф
Ф	Ф	Т

3.

Составьте таблицу истинности для утверждения \ (\ neg P \ wedge (Q \ imp P) \ text {.} \) Что вы можете сделать в отношении \ (P \) и \ (Q \), если знаете, что утверждение правда?

Решение

\ (П \)	\ (Q \)	\ (\ neg P \ клин (Q \ imp P) \)
т	Т	Ф
т	Ф	Ф
Ф	Т	Ф
Ф	Ф	Т

Если утверждение верно, то и \ (P \), и \ (Q \) ложны.

4.

Составьте таблицу истинности для утверждения \ (\ neg P \ imp (Q \ wedge R) \ text {.} \)

Подсказка

Как и выше, только теперь вам понадобится 8 рядов вместо 4.

5.

Джефф Пошингтен выходит в модную пиццерию и решает заказать кальцоне. Когда официант спрашивает, что бы он хотел, он отвечает: «Я хочу пепперони или колбасу. Также, если у меня есть колбаса, то я должен еще включить перепелов. Да, и если у меня есть пепперони или перепела, то мне также нужен сыр рикотта.”

Переведите приказ Джеффа в логические символы.
Официант знает, что Джефф либо лжец, либо говорит правду (так что либо все, что он говорит, либо ложь, либо все правда). Что он?
Что может сделать официант об ингредиентах в кальцоне, который Джефф пожелал?

Намекать

Вы должны записать три утверждения, используя символы \ (P, Q, R, S \ text {.} \). Если Джефф говорит правду, то все три утверждения будут верными.Если бы он был лжецом, то все три утверждения были бы ложными. Но в любом случае мы еще не знаем, истинны или ложны четыре атомарных утверждения, поскольку он не сказал их сами по себе.

Таблица истинности может помочь, хотя, вероятно, не совсем необходима.

6.

Определите, являются ли следующие два утверждения логически эквивалентными: \ (\ neg (P \ imp Q) \) и \ (P \ wedge \ neg Q \ text {.} \). Объясните, откуда вы знаете, что вы правы.

Решение

Составьте таблицу истинности для каждого и сравните.Эти утверждения логически эквивалентны.

7.

Являются ли утверждения \ (P \ imp (Q \ vee R) \) и \ ((P \ imp Q) \ vee (P \ imp R) \) логически эквивалентными?

8.

Упростите следующие утверждения (чтобы отрицание появлялось только непосредственно перед переменными).

\ (\ neg (P \ imp \ neg Q) \ text {.} \)
\ ((\ neg P \ vee \ neg Q) \ imp \ neg (\ neg Q \ wedge R) \ text {.} \)
\ (\ neg ((P \ imp \ neg Q) \ vee \ neg (R \ wedge \ neg R)) \ text {.} \)
Неверно, что если Сэм не мужчина, то Крис — женщина, а Крис — не женщина.

Решение

\ (P \ wedge Q \ text {.} \)
\ ((\ neg P \ vee \ neg R) \ imp (Q \ vee \ neg R) \) или, сначала заменив импликацию дизъюнкцией: \ ((P \ wedge Q) \ vee (Q \ vee \ негр R) \ text {.} \)
\ ((P \ wedge Q) \ wedge (R \ wedge \ neg R) \ text {.} \) Это обязательно неверно, поэтому оно также эквивалентно \ (P \ wedge \ neg P \ text {. } \)
Либо Сэм — женщина, а Крис — мужчина, либо Крис — женщина.

9.

Используйте законы Де Моргана и любые другие известные вам факты логической эквивалентности, чтобы упростить следующие утверждения. Покажи все свои шаги. В ваших заключительных утверждениях отрицания должны появляться только непосредственно рядом с переменными предложения или предикатами (\ (P \ text {,} \) \ (Q \ text {,} \) \ (E (x) \ text {,} \) и т. д.), и никаких двойных отрицаний. Было бы неплохо использовать только союзы, дизъюнкции и отрицания.

\ (\ neg ((\ neg P \ wedge Q) \ vee \ neg (R \ vee \ neg S)) \ text {.} \)
\ (\ neg ((\ neg P \ imp \ neg Q) \ wedge (\ neg Q \ imp R)) \) (осторожно с последствиями).
Для обеих приведенных выше частей проверьте правильность ответов с помощью таблиц истинности. То есть используйте таблицу истинности, чтобы проверить, что данное утверждение и предлагаемое вами упрощение фактически логически эквивалентны.

10.

Рассмотрим утверждение: «Если число треугольное или квадратное, то оно не простое»

Составьте таблицу истинности для утверждения \ ((T \ vee S) \ imp \ neg P \ text {.} \)
Если вы считаете, что это утверждение было ложным , какими свойствами должен обладать контрпример? Объясните, ссылаясь на вашу таблицу истинности.
Если бы утверждение было верным, какой бы вы могли сделать вывод о числе 5657, которое определенно простое? Опять же, объясните, используя таблицу истинности.

Подсказка

Будет три строки, в которых утверждение ложно.
Рассмотрим три строки, которые оцениваются как ложные, и говорят, какие истинные значения для \ (T \ text {,} \) \ (S \ text {,} \) и \ (P \) присутствуют.
Вы ищете строку, в которой \ (P \) истинно, а все утверждение истинно.

11.

Томми Фланаган рассказывал вам, что он ел вчера днем. Он говорит вам: «Я ел либо попкорн, либо изюм. Кроме того, если у меня были бутерброды с огурцами, то у меня была газировка. Но я не пил газировку или чай ». Конечно, вы знаете, что Томми — худший лжец в мире, и все, что он говорит, — ложь. Что ел Томми?

Обоснуйте свой ответ, записав все утверждения Томми, используя переменные предложения (\ (P, Q, R, S, T \)), взяв их отрицания и используя их, чтобы вывести, что на самом деле ел Томми.

Подсказка

Запишите три утверждения, а затем возьмите отрицание каждого (поскольку он лжец). Вы должны обнаружить, что Томми съел одно блюдо и выпил одно. (\ (Q \) для бутербродов с огурцами.)

12.

Определите, действительно ли следующее правило вычета:

	\ (P \ vee Q \)
	\ (\ neg P \)
\ (\ следовательно \)	\ (Q \)

Решение

Правило вычета действительно.Чтобы убедиться в этом, составьте таблицу истинности, которая содержит \ (P \ vee Q \) и \ (\ neg P \) (и, конечно, \ (P \) и \ (Q \)). Посмотрите на значение истинности \ (Q \) в каждой из строк, в которых есть \ (P \ vee Q \) и \ (\ neg P \) true.

13.

Определите, является ли следующее действительным правилом вычета:

	\ (П \ имп (Q \ vee R) \)
	\ (\ neg (P \ imp Q) \)
\ (\ следовательно \)	\ (R \)

14.

Определите, является ли следующее действительным правилом вычета:

	\ ((P \ клин Q) \ имп R \)
	\ (\ neg P \ vee \ neg Q \)
\ (\ следовательно \)	\ (\ neg R \)

15.

Можете ли вы связать последствия вместе? То есть, если \ (P \ imp Q \) и \ (Q \ imp R \ text {,} \) означает, что это означает \ (P \ imp R \ text {?} \). Можете ли вы связать вместе другие импликации? Выясним:

Докажите, что следующее действительное правило вычета:
\ (П \ имп Q \)
\ (Q \ имп R \)
\ (\ следовательно \) \ (П \ имп R \)

Докажите, что следующее действительное правило вычета для любого \ (n \ ge 2 \ text {:} \)

\ (P_1 \ imp P_2 \)

\ (P_2 \ имп P_3 \)

\ (\ vdots \)

\ (P_ {n-1} \ imp P_n \)

\ (\ следовательно \)

\ (P_1 \ imp P_n \ text {.n \) строка таблицы истинности. Вместо этого вы должны использовать часть (а) и математическую индукцию.

Подсказка

Для второй части вы можете индуктивно предположить, что из первого \ (n-2 \) импликации вы можете вывести \ (P_1 \ imp P_ {n-1} \ text {.} \). Затем вы вернетесь в дело в части (а) снова.

16.

Мы также можем упростить утверждения в логике предикатов, используя наши правила передачи отрицаний кванторам, а затем применяя пропозициональную логическую эквивалентность к «внутренней» пропозициональной части.Упростите приведенные ниже утверждения (чтобы отрицание появлялось только непосредственно рядом с предикатами).

\ (\ neg \ exists x \ forall y (\ neg O (x) \ vee E (y)) \ text {.} \)
\ (\ neg \ forall x \ neg \ forall y \ neg (x \ lt y \ wedge \ exists z (x \ lt z \ vee y \ lt z)) \ text {.} \)
Существует число \ (n \), для которого никакое другое число не меньше \ (n \), чем или равно \ (n \ text {.} \)
Неверно, что для каждого числа \ (n \) есть два других числа, между которыми находится \ (n \).

Решение

\ (\ forall x \ exists y (O (x) \ wedge \ neg E (y)) \ text {.} \)
\ (\ существует x \ forall y (x \ ge y \ vee \ forall z (x \ ge z \ wedge y \ ge z)) \ text {.} \)
Существует число \ (n \), для которого любое другое число строго больше, чем \ (n \ text {.} \)
Есть число \ (n \), которого нет между двумя другими числами.

17.

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

\ (\ neg \ forall x \ forall y (x \ lt y \ vee y \ lt x) \ text {.} \)
\ (\ neg (\ exists x P (x) \ imp \ forall y P (y)) \ text {.} \)

18.

Упрощение отрицаний будет особенно полезно в следующем разделе, когда мы попытаемся доказать утверждение, рассмотрев, что произошло бы, если бы оно было ложным. Для каждого утверждения ниже напишите как можно проще отрицание утверждения. Не говорите просто: «Это неправда…».

Каждое число четное или нечетное.
Существует арифметическая и геометрическая последовательность.
Для всех чисел \ (n \ text {,} \), если \ (n \) простое, то \ (n + 3 \) не простое.

Подсказка

Может помочь перевести утверждения в символы, а затем использовать формульные правила для упрощения отрицаний (то есть правила для кванторов и законы Де Моргана). После упрощения вы должны получить, например, \ (\ forall x (\ neg E (x) \ wedge \ neg O (x)) \ text {,} \).Затем переведите это обратно на английский.

19.

Предположим, что \ (P \) и \ (Q \) — (возможно, молекулярные) пропозициональные утверждения. Докажите, что \ (P \) и \ (Q \) логически эквивалентны, если они есть, только если \ (P \ тогда и только тогда, когда Q \) — тавтология.

Подсказка

Что означают эти концепции в терминах таблиц истинности?

20.

Предположим, что \ (P_1, P_2, \ ldots, P_n \) и \ (Q \) являются (возможно, молекулярными) пропозициональными утверждениями. Предположим далее, что

	\ (P_1 \)
	\ (P_2 \)
	\ (\ vdots \)
	\ (П_н \)
\ (\ следовательно \)	\ (Q \)

— действительное правило вычета.Докажите, что утверждение

\ begin {уравнение *} (P_1 \ клин P_2 \ клин \ cdots \ клин P_n) \ imp Q \ end {уравнение *}

— это тавтология.

дизъюнкция в nLab

Логическая дизъюнкция

Контекст

(0,1) (0,1) -Теория категорий

Определения

В логике логическая дизъюнкция — это соединение в наборе значений истинности.

Предполагая, что (как в классической логике) единственными значениями истинности являются истина (TT) и ложь (FF), тогда дизъюнкция p∨qp \ vee q значений истинности pp и qq может быть определена таблицей истинности:

9024 9024 9024 9024 TT 9024 9024 9024 TT

pp	qq	p∨qp \ vee q
TT	TT	TT
	TT
FF	FF	FF

То есть p∨qp \ vee q истинно тогда и только тогда, когда хотя бы одно из pp и qq истинно.Дизъюнкция также существует почти во всех неклассических логиках.

В более общем смысле, если pp и qq — любые два отношения в одной и той же области, то мы определяем их дизъюнкцию поточечно, думая об отношении как о функции значений истинности. Если вместо этого мы думаем об отношении как о подмножестве его области, то дизъюнкция становится объединением.

Дизъюнкция, как определено выше, иногда называют включающей дизъюнкцией , чтобы отличить ее от исключительной дизъюнкции, где ровно одно из pp и qq должно быть истинным.

В контексте субструктурной логики, такой как линейная логика, мы часто имеем как аддитивную дизъюнкцию ⊕ \ oplus, так и мультипликативную дизъюнкцию ⅋ \ parr; см. Правила вывода ниже для различия. В линейной логике аддитивная дизъюнкция — это соединение в соответствии с отношением следования, точно так же, как дизъюнкция в классической логике (и интуиционистской логике), в то время как мультипликативная дизъюнкция — это нечто иное.

Дизъюнкция двойственна конъюнкции де Моргана.

Как и любое соединение, дизъюнкция является ассоциативной операцией, поэтому мы можем взять дизъюнкцию любого конечного положительного целого числа истинностных значений; дизъюнкция истинна тогда и только тогда, когда истинно хотя бы одно из различных значений истинности. Дизъюнкция также имеет элемент идентичности, который является значением ложной истины. Некоторые логики допускают понятие бесконечной дизъюнкции. Индексированная дизъюнкция — это экзистенциальная количественная оценка.

В теории гомотопических типов дизъюнкция двух простых предложений, PP и QQ, является скобочным типом их типа суммы, ‖P + Q‖ \ | Р + Q \ |.Типы дизъюнкции в целом также можно рассматривать как особый вид высшего индуктивного типа. В синтаксисе Coq:

  Индуктивная дизъюнкция (P Q: Тип): Тип: =
| inl: P -> дизъюнкция P Q
| inr: Q -> дизъюнкция P Q
| contr0: forall (p q: дизъюнкция P Q) p == q

Классическое и конструктивное

Существует множество связок, которые различны в интуиционистской логике, но все эквивалентны дизъюнкции в классической логике. Вот диаграмма Хассе некоторых из них, с самым сильным утверждением внизу и самым слабым вверху (так что каждое утверждение влечет за собой те, которые находятся над ним):

¬ (¬P∧¬Q) ⇗⇖¬P → QP ← ¬Q⇖⇗ (¬P → Q) ∧ (P ← ¬Q) ⇑P∨Q \ array {& & \ neg (\ neg {P} \ клин \ neg {Q}) \\ & & # x21d7; & & # x21d6; \\ \ neg {P} \ rightarrow Q & & & & P \ leftarrow \ neg {Q} \\ & & # x21d6; & & # x21d7; \\ & & (\ neg {P} \ rightarrow Q) \ wedge (P \ leftarrow \ neg {Q}) \\ & & \Стрелка вверх \\ & & P \ vee Q}

(Одиночная стрелка подразумевает объектный язык; двойная стрелка подразумевает метаязык.) Обратите внимание, что ¬P∧¬Q \ neg {P} \ wedge \ neg {Q} — это отрицание каждого элемента на этой диаграмме.

В интерпретации двойного отрицания? классической логики в интуиционистской логике ¬ (¬P∧¬Q) \ neg (\ neg {P} \ wedge \ neg {Q}) — это интерпретация в интуиционистской логике дизъюнкции в классической логике. По этой причине ¬ (¬P∧¬Q) \ neg (\ neg {P} \ wedge \ neg {Q}) иногда называют классической дизъюнкцией . Но это не означает, что его следует всегда использовать при превращении классической математики в конструктивную математику.В самом деле, более сильное утверждение почти всегда предпочтительнее, если оно действительно; ¬ (¬P∧¬Q) \ neg (\ neg {P} \ wedge \ neg {Q}) — это просто резервная позиция, когда ничего лучше не найти. (И, как видно из примера в абзаце после следующего, иногда даже это неверно.)

В противоположной интерпретации аффинной логики в интуиционистской логике (¬P → Q) ∧ (P ← ¬Q) (\ neg {P} \ rightarrow Q) \ wedge (P \ leftarrow \ neg {Q}) является интерпретацией мультипликативной дизъюнкции P⅋QP \ parr Q для утвердительных предложений.-). Обратите внимание, что P⊕QP \ oplus Q влечет за собой P⅋QP \ parr Q в аффинной логике, хотя они независимы в линейной логике.)

Для отрицательного примера, в арифметике (обнаруженных) действительных чисел, конструктивно некорректно выводить (a = 0) ∨ (b = 0) (a = 0) \ vee (b = 0) из ab = 0a b = 0, и даже неверно вывести ¬ (¬ (a = 0) ∧¬ (b = 0)) \ neg \ big (\ neg (a = 0) \ wedge \ neg (b = 0) \ big) без принципа Маркова (или, по крайней мере, в какой-то его слабой версии), но действительно для вывода (a # 0) → (b = 0) (a \ # 0) \ rightarrow (b = 0) ( и наоборот), где # \ # — обычное отношение разделения между действительными числами.- это # 0a \ # 0, и аналогично для QQ и bb.) Конечно, также можно вывести ¬ ((a # 0) ∧ (b # 0)) \ neg \ big ((a \ # 0) \ wedge (b \ # 0) \ big) (что на самом деле эквивалентно).

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

Правила вывода для дизъюнкции в исчислении секвенций двойственны правилам вывода для конъюнкции:

Γ, p, Δ⊢Σ; Γ, q, Δ⊢ΣΓ, p∨q, Δ⊢Σ левая добавка Γ⊢Δ, p, ΣΓ⊢Δ, p∨q, Σ правая добавка 0Γ⊢Δ, q, ΣΓ⊢Δ, p ∨q, Σправая добавка 1 \ begin {gather} \ frac {\ Gamma, p, \ Delta \ vdash \ Sigma; \; \ Gamma, q, \ Delta \ vdash \ Sigma} {\ Gamma, p \ vee q, \ Delta \ vdash \ Sigma} \; \ text {левая добавка} \\ \ frac {\ Gamma \ vdash \ Delta, p, \ Sigma} {\ Gamma \ vdash \ Delta, p \ vee q, \ Sigma} \; \ text {правая добавка 0} \\ \ frac {\ Gamma \ vdash \ Delta, q, \ Sigma} {\ Gamma \ vdash \ Delta, p \ vee q, \ Sigma} \; \ text {правая добавка 1} \\ \ end {собрано}

Аналогично, мы можем использовать следующие правила с ослабленными контекстами:

Γ, p⊢Δ; q, Σ⊢ΠΓ, p∨q, Σ⊢Δ, Πлевая мультипликативная Γ⊢Δ, p, q, ΣΓ⊢Δ, p∨q, Σправая мультипликативная \ begin {gather} \ frac {\ Gamma, p \ vdash \ Delta; \; q, \ Sigma \ vdash \ Pi} {\ Gamma, p \ vee q, \ Sigma \ vdash \ Delta, \ Pi} \; \ text {левый мультипликативный} \\ \ frac {\ Gamma \ vdash \ Delta, p, q, \ Sigma} {\ Gamma \ vdash \ Delta, p \ vee q, \ Sigma} \ text {правый мультипликативный} \\ \ end {собрано}

Приведенные выше правила написаны так, чтобы оставаться действительными в логике без правила обмена.В линейной логике первый набор последовательных правил применяется к аддитивной дизъюнкции (интерпретируйте p∨qp \ vee q в этих правилах как p⊕qp \ oplus q), а второй набор правил применяется к мультипликативной дизъюнкции (интерпретируйте p∨qp \ vee q в этих правилах как p⅋qp \ parr q).

Правила естественного вывода для дизъюнкции немного сложнее, чем для конъюнкции:

Γ, p⊢r; Γ, q⊢rΓ, p∨q⊢reliminationΓ⊢pΓ⊢p∨qintroduction 0Γ⊢qΓ⊢p∨qintroduction 1 \ begin {gather} \ frac {\ Gamma, p \ vdash r; \; \ Gamma, q \ vdash r} {\ Gamma, p \ vee q \ vdash r} \; \ text {исключение} \\ \ frac {\ Gamma \ vdash p} {\ Gamma \ vdash p \ vee q} \; \ текст {введение 0} \\ \ frac {\ Gamma \ vdash q} {\ Gamma \ vdash p \ vee q} \; \ текст {введение 1} \\ \ end {собрано}

основных символа, используемых в логике

Список литературы

Таблица истинности — Энциклопедия математики

Математика 2010 Классификация предметов: Начальная школа: 03-XX [MSN] [ZBL]

Таблица истинности таблица, выражающая значения истинности сложного предложения в терминах значений истинности простых предложений, составляющих его (см.