Логические операции

Логические операции

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

Логическое отрицание (инверсия inverso – лат. переворачивание )

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

Обозначение: НЕ U ;  U ; Ū ; NOT U

Высказывание U

Значение высказывания

Я люблю петь

Инверсия

Ū

1

Значение инверсии

Я НЕ люблю петь

0

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

Таблица

истинности

Инверсия высказывания истинна, когда высказывание ложно, и ложна, когда высказывание истинно.

U

Ū

0

1

1

0

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

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

Графическая иллюстрация

Высказывание, отрицающееся кратное число раз, имеет то же значение истинности, что и исходное высказывание.

Высказывание, отрицающееся не кратное число раз, имеет то же значение истинности, что и инверсия высказывания.

А= Неверно, что математика не царица наук.

НЕ Х

Х

 Х

Х – множество учащихся

НЕ Х – множество не учащихся

В теории множеств соответствует операция – дополнение множества

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

образуется соединением двух высказываний в одно с помощью союза И

Обозначение: А И В; А  В; А & В; А · В; А AND В

А= В саду цвели астры

В = В саду цвели пионы

А & В = В саду цвели астры и пионы

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

Таблица

истинности

А & В = В саду цвели астры и пионы

А

Астры не цвели

В

А И В

Астры не цвели

Пионы не цвели

Астры цвели

Ложь

Пионы цвели

Астры цвели

Пионы не цвели

Ложь

Пионы цвели

Ложь

Истина

А

0

В

0

А И В

0

1

0

1

1

0

0

1

0

1

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

Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно высказывание ложно

Мнемоническое правило:

конъюнкция – это логическое умножение.

Равенства 0 · 0=0; 0 · 1=0; 1 · 0=0; 1 · 1=1, верные для обычного умножения, верны и для операции конъюнкции

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

В теории множеств соответствует операция – пересечение множеств

Графическая иллюстрация

А – множество учащихся

В – множество танцоров

С= А  В – множество учащихся, занимающихся танцами

В

С

А

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

образуется соединением двух высказываний в одно с помощью союза ИЛИ

Дизъюнкция

Строгая

Нестрогая

- союз ИЛИ разъединяющий

• союз ИЛИ

объединяющий

Строгая и нестрогая дизъюнкция

Петя сидит на западной или восточной трибуне стадиона

Строгая

Нестрогая

Студент едет в электричке или читает книгу

Он учится в школе или окончил ее

Строгая

Числа можно складывать или перемножать

Нестрогая

Оля любит писать сочинения или решать задачи

Нестрогая

Земля движется по круговой или эллиптической орбите

Строгая

Завтра дождь будет или не будет

Строгая

Нестрогая (дизъюнкция)

Обозначение: А ИЛИ В; А  В; А  В; А + В; А OR В

Таблица

истинности

А  В = В саду цвели астры ИЛИ пионы

А

Астры не цвели

В

А  В

Астры не цвели

Пионы не цвели

Астры цвели

Ложь

Пионы цвели

Астры цвели

Пионы не цвели

Истина

Пионы цвели

Истина

Истина

А

0

В

0

0

А  В

0

1

1

1

0

1

1

1

1

Нестрогая дизъюнкция

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

Мнемоническое правило:

дизъюнкция – это логическое сложение. Равенства 0 +0=0; 0 +1=1; 1 +0=1, верные для обычного умножения, верны и для операции дизъюнкции, но 1  1=1.

Символ  (дизъюнкция) образован из первой буквы слова Vel ( «или»).

В слове конъюнкция одна буква И, в слове дизъюнкция – две буквы И, как и в слове ИЛИ.

Нестрогая дизъюнкция

В теории множеств соответствует операция – объединение множеств

Графическая иллюстрация

А – множество спортсменов

В – множество танцоров

А  В – множество учащихся, занимающихся танцами или спортом

В

А

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

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

Обозначение: А → В; А ⇒ В

Если число делится на 9, то оно делится на 3

Если А, то В; А имплицирует В; А влечет В; В следует из А

Если на улице дождь, то асфальт мокрый

Если коровы летают, то 2+2=5

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

А= На улице дождь

В = Асфальт мокрый

(А ⇒ В) = Если на улице дождь, то асфальт мокрый

Таблица

истинности

А

Дождя нет

В

Дождя нет

Асфальт сухой

А ⇒ В

Дождь идет

Истина

Асфальт мокрый

Дождь идет

Асфальт сухой

Истина

Асфальт мокрый

Ложь

Истина

А

0

В

А ⇒ В

0

0

1

1

1

1

1

0

0

1

1

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

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

Графическая иллюстрация

В

А

В

В

В

А

А

А

(А =0) ∩ (В=0)

(А =0) ∩ (В=1)

(А =1) ∩ (В=1)

Логическое равенство (эквивалентность)

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

Обозначение: А ≡ В; А ⇔ В; А ~ В

(А ⇔ В) = Угол называется прямым тогда и только тогда, когда он равен 90 º .

Если А, то В; А имплицирует В; А влечет В; В следует из А

В = Угол равен 90 º

А = Угол прямой

(А ⇔ В) = Голова думает тогда и только тогда, когда язык отдыхает.

Логическое равенство (эквивалентность)

А= Число делится на 3 без остатка (кратно 3)

В = Сумма цифр числа делится нацело на 3

(А ⇔ В) = Число кратно 3 тогда и только тогда, когда сумма его цифр делится нацело на 3

Таблица

истинности

А

А

Число не кратно 3

0

В

В

Число не кратно 3

Сумма цифр не кратна 3

А ⇔ В

А ⇔ В

0

0

Истина

1

Число кратно 3

1

Сумма цифр кратна 3

1

Число кратно 3

1

0

Ложь

0

Сумма цифр не кратна 3

Ложь

Сумма цифр кратна 3

0

1

1

Истина

Логическое равенство (эквивалентность)

Эквивалентность двух высказываний истинна тогда и только тогда, когда оба высказывания истинны или оба ложны.

Графическая иллюстрация

В

А

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

высказывание ложно

ложны

оба высказывания

истинны

истинно

хотя бы одно высказывание

ложно

из истинного высказывания

следует ложное высказывание

оба высказывания истинны

или оба высказывания ложны

Инверсия истинна

Дизъюнкция ложна

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

Дизъюнкция истинна

Конъюнкция ложна

Импликация ложна

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

тогда

и

только

тогда,

когда

Логические формулы

А,В – логические переменные

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

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

• скобки
• инверсия;
• конъюнкция;
• дизъюнкция;
• импликация и эквивалентность.

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

Скобки; инверсия; конъюнкция; дизъюнкция; импликация и эквивалентность

Пример 1.

U  В ⇒ С & D ⇔ Ū

Порядок вычисления:

1) Ū

2) С & D

3) U  В

4) U  В ⇒ С & D

5) U  В ⇒ С & D ⇔ Ū

Пример 2.

U  (В ⇒ С) & D ⇔ Ū

Порядок вычисления:

1) Ū

2) (В ⇒ С)

3) (В ⇒ С) & D

4) U  (В ⇒ С) & D

5) U  В ⇒ С & D ⇔ Ū

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

инверсия; конъюнкция; дизъюнкция; импликация и эквивалентность

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

Е = К  Ū ⇒ Ӣ

1.Определить число простых высказываний n.

2.Вычислить количество строк ( 2 n +2) и столбцов (n+число операций).

3. Начертить таблицу и заполнить заголовок.

4. Заполнить столбцы простых высказываний:

1 столбец: 2 n /2=k (чередуем k нулей и k единиц);

2 столбец: k/2=m (чередуем m нулей и m единиц);

3 столбец: m/2=p (чередуем p нулей и p единиц)/

5. Заполнить остальные столбцы соответственно логическим формулам

Значение сложного высказывания определяется по таблице истинности. Число строк в таблице равно 2 n +2 , так как каждое простое высказывание может принимать два значения (0 и 1), то число комбинаций будет 2 n , и 2 строки на заголовки. Число столбцов равно сумме простых высказываний и числу логических операций.

Типы сложных высказываний

Тождественно истинное (тавтология) – высказывание истинно при всех значениях входящих в него переменных ( обозначается константой 1): U  Ū

Дождь будет или дождя не будет

Тождественно ложное – высказывание ложно при всех значениях входящих в него переменных (обозначается константой 0): U & Ū

Компьютер включен и не включен

• Дождь будет или дождя не будет.
• Компьютер включен и не включен.

Тождественные (равносильные, эквивалентные) – высказывания, значения которых совпадают при всех возможных значениях входящих переменных: А=В