Теория алгоритмов. (Лекция 3) презентация

СВОЙСТВА АЛГОРИТМОВ

Логика – наука о формах и способах мышления Логика – наука о формах и способах мышления

Логическое умножение (конъюнкция) - объединение двух или более высказываний в одно при помощи операции «И».

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

Логическое сложение (дизъюнкция)- объединение двух или более высказываний в одно при помощи союза «ИЛИ»

Логическое сложение (дизъюнкция) Пример 2.

Логическое отрицание (инверсия) – присоединение частицы «не» к высказыванию

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

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

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

(AVB) <=> (C&D) (A&B) -> (CVD) (AVB) -> (C&D) (A&B) <=> (CVD) (Ā -> B)&(CVD) (C <=> Ā)&B&D (A&B)VC <=> (A&C)V(A&B) (AVB)VC -> (A&C&D)&(BVD)

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

ЛОГИЧЕСКИЕ ФУНКЦИИ Любое составное высказывание можно рассматривать как логическую функцию F(X1, X2, …, XN), аргументами которой являются логические переменные X1, X2, …, XN - простые высказывания. Функция и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0).

Пример 6. Правило де Моргана: (x & у) = x V y

Пусть истинна правая часть, т. е. x = 1, тогда в левой части дизъюнкция x v (x & у) истинна. Пусть истинна правая часть, т. е. x = 1, тогда в левой части дизъюнкция x v (x & у) истинна. Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула x, или формула (x & у), или обе эти формулы одновременно. Если x ложна, тогда (x & у) ложна, следовательно, x может быть только истинной.

x V (x & у ) = (x & 1 ) V (x & у ) = x & (1 V y) = x x V (x & у ) = (x & 1 ) V (x & у ) = x & (1 V y) = x

Формула А называется Формула А называется тавтологией (или тождественно истинной), если она истинна при любых значениях своих переменных. Пример 9. х V х =1 (операция переменной с её инверсией)

Формула А называется тождественно ложной, Формула А называется тождественно ложной, если она равна 0 при любых значениях своих переменных. Пример 10. х & х =0

Пример 11. Определить x, если: (x V a) V (x V a) = b

Пример 12. Какие формулы являются тавтологиями? (a & a) a  (b  a) (a & b)  a

1) (a & a)

2) a  (b  a)

3) (a & b)  a

Пример 13. Является ли формула тождественно ложной? a & (a  b) & (a  b)

F1 = {если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3}; F1 = {если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3}; F2 = {если одно слагаемое делится на 3, а другое не делится на 3, то сумма не делится на 3}. Формализуйте эти высказывания, постройте таблицы истинности для каждой из полученных формул и убедитесь, что результирующие столбцы совпадают.

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

На вопрос «Кто из трех студентов изучал логику?», был получен ответ: На вопрос «Кто из трех студентов изучал логику?», был получен ответ: «Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?

А = {А получит максимальную прибыль}, А = {А получит максимальную прибыль}, В = {В получит максимальную прибыль}, С = {С получит максимальную прибыль}. F1 = А  В & С; F2 = А & С v А & С; F3 = С  В.

Таблица истинности для F1 , F2 , F3