Шинкаренко Евгений Александрович МОУ Гимназия 2 г.Черняховск Калининградской области. - презентация

1 Шинкаренко Евгений Александрович МОУ Гимназия 2 г.Черняховск Калининградской области

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

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

4 В данном примере истинно только 4-ое составное высказывание.

5 Формула функции логического умножения: F = A B. Значение логической функции можно определить с помощью таблицы истинности данной функции: АВF = A B

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

7 В данном примере ложно только 1-ое составное высказывание.

8 Формула функции логического сложения: F = A B. Значение логической функции можно определить с помощью таблицы истинности данной функции: АВ F = A B

9 Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией. Обозначение операции инверсия: F = ¬ A, «не». Логическое отрицание делает истинное высказывание ложным и, наоборот, ложное – истинным.

10 Таблица истинности функции логического отрицания А F = ¬ A 01 10

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

12 «(2*2=5 или 2*2=4) и (2*25 или 2*24)» А = «2*2=5» - ложно (0), ¬А= «2*25» – истина (1), В = «2*2=4» - истинно (1), ¬В= «2*24» – ложно (0). «(А или В) и (¬А или ¬В)» F = (А В) (¬А ¬В) = (0 1) (1 0) = 1 1 = 1

13 Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая определяет его истинность или ложность при всех возможных комбинациях исходных значений простых высказываний (логических переменных). Количество строк в таблице истинности равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение. Если N-переменных, то количество строк = 2 N Количество столбцов = количество логических переменных + количеству логических операций.

14 Построим таблицу истинности для F = (А В) (¬А ¬В) АВ А В ¬А¬В ¬А ¬В(А В) (¬А ¬В)

15 Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используют знак « = ». Докажем равносильность следующих логических выражений: ¬А ¬В и ¬(А В)

16 Таблица истинности для ¬А ¬В Таблица истинности для ¬(А В) ¬А ¬В = ¬(А В) АВ¬А¬В ¬А ¬В АВ А В¬(А В)

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

18 Таблица истинности логической функции «импликации» В алгебре высказываний все логические функции могут быть сведены путем логических преобразований к трем базовым: логическому умножению, логическому сложению и логическому отрицанию. АВF=АВ

19 Докажем методом сравнения таблиц истинности АВ = ¬А В АВАВ АВ¬А ¬А В

20 Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «А тогда и только тогда, когда В». Логическая операция эквивалентности обозначается F=А~B. Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.

21 Таблица истинности логической функции эквивалентности АВF=А~B

22 Докажем методом сравнения таблиц истинности А~B = (А ¬В) (¬А В) АВ¬А¬В А ¬В¬А В(А ¬В) (¬А В) АВА~B

23 Логическое умножение (конъюкция): &,, «и» Логическое сложение (дизъюнкция): +,, «или» Логическое отрицание (инверсия): F = ¬ A, «не» Логическое следование (имплексия): АВ, «если А, то В» АВ = ¬А В Логическое равенство (эквивалентность): А~В, «А тогда и только тогда, когда В» А~B = (А ¬В) (¬А В) Закон непротиворечия: А ¬ А = 0; Закон исключённого третьего: А ¬ А = 1; Закон двойного отрицания: ¬ ¬ А = А; Законы де Моргана: ¬ (А В) = ¬ А ¬ В; ¬ (А В) = ¬ А ¬ В; Закон коммутативности: А В = В А; А В = В А; Закон ассоциативности: (А В) С = А (В С) = А В С (А В) С = А (В С) = А В С Дистрибутивность умножения относительно сложения: (А В) (А С) = А (В С) Дистрибутивность сложения относительно умножения: (А В) (А С) = А (В С)

24 Доказать при помощи таблиц истинности равносильность следующих выражений ¬ (А В) = ¬ А ¬ В;