Алгебра высказываний. Логические функции.

Алгебра высказываний. Логические функции.

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

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

Высказывание может быть истинно или ложно.

Алгебра высказываний.

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

Алгебра высказываний

В алгебре высказываний суждениям (простым высказываниям) ставятся в соответствие

логические переменные

(заглавные латинские буквы).

Например:

А – «2*2=4»

В – «2*2=5»

• А – «2*2=4» В – «2*2=5»

Алгебра высказываний

Высказывания, как уже говорилось могут быть истинными или ложными. Истинному высказыванию соответствует значение логической переменной 1 , а ложному – 0.

В нашем примере первое высказывание истинно (А=1),

второе – ложно (В=0).

Алгебра высказываний

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

Логические выражения

Логические величины : понятия, выраженные словами: ИСТИНА, ЛОЖЬ ( true , false ).

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

Логическая константа : ИСТИНА или ЛОЖЬ.

Логическая переменная : символически обозначается логическая величина.

Следовательно, если известно, что А, В, Х, У и пр. – переменные логические величины, то это значит, что они могут принимать значения только ИСТИНА или ЛОЖЬ .

Логические выражения

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

Логическое выражение – простое или сложное высказывание.

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

Логические выражения

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

Результатом вычисления логической формулой является ИСТИНА или ЛОЖЬ.

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

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

В русском языке она выражается союзом И .

В математической логике используются знаки & или  .

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

Конъюнкция – двухместная операция; записывается в виде: А  В.

Значение такого выражения будет ЛОЖЬ, если хотя бы значение одного из операндов ложно.

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

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

В русском языке она выражается союзом ИЛИ.

В математической логике она обозначается знаком  .

Дизъюнкция - двухместная операция; записывается в виде: А  В.

Значение такого выражения будет ИСТИНА, если значение хотя бы одного из операндов истинно .

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

Отрицание ( Инверсия ) .

В русском языке этой связке соответствует частица

НЕ (в некоторых высказываниях применяется оборот

«неверно, что…»).

Отрицание – унарная (одноместная) операция; записывается в виде:

 А или А .

Отрицание ( Инверсия ) .

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

Если…То

Логическая операция импликация «Если А то В», обозначается А  В .

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

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

А

В

0

А  В

0

0

1

1

1

1

0

1

1

0

1

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

Например:

«Если число делится на 10 , то оно делиться на 5»

«Если число делится на 10 , то оно делиться на 3» ложно.

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

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

Обозначается А  В и истинно тогда и только тогда, когда оба высказывания одновременно либо ложно, либо истинны.

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

А

В

0

А  В

0

0

1

1

1

0

0

1

1

0

1

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

Например:

«Компьютер может производить вычисления, тогда и только тогда, когда компьютер включен»

«Компьютер не может производить вычисления, тогда и только тогда, когда компьютер не включен»

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

«Компьютер может производить вычисления, тогда и только тогда, когда компьютер не включен»

«Компьютер не может производить вычисления, тогда и только тогда, когда компьютер включен»

Приоритет операций

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

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

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

Логические схемы

Приоритет операций

Например:

(А и В) или ( не А и В) или ( не А и не В).

Пример 4. Вычислить значение логической формулы: не Х и У или Х и Z , если логические переменные имеют следующие значения: Х = ЛОЖЬ, У = ИСТИНА, Z = ИСТИНА.

Решение. Отметим цифрами сверху порядок выполнения операций в выражении:

1 2 4 3

не Х и У или Х и Z

Задачи

2. " width="640"

Задачи

Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ»:

Например:

Все ученики изучают математику. Все ученики изучают литературу.

Все ученики изучают математику и литературу

• Марина старше Светы. Оля старше Светы.
• Одна половина класса изучает английский язык. Вторая половина класса изучает немецкий язык.
• В кабинете есть учебники. В кабинете есть справочники.
• Слова в этом предложении начинаются на букву Ч. Слова в этом предложении начинаются на букву А.
• Часть туристов любит чай. Остальные туристы любят молоко.
• Синий кубик меньше красного. Синий кубик меньше зеленого.
• Х = 3, Х 2.