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

1 1. Историческая справка Булева алгебра. 3 3 Логические выражения. Логические выражения. 3.1 Логическое отрицание. Логическое отрицание. 3.2 Логическое сложение. Логическое сложение. 3.3 Логическое умножение. Логическое умножение. 3.4 Логическое следование. Логическое следование. 3.5 Эквивалентность. Эквивалентность Построение таблиц Основные законы логики.

Немецкий ученый Лейбниц в 1666 году впервые попытался перевести законы мышления ( формальную логику ) из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются в виде математических соотношений. Спустя более ста лет, в 1816 году, уже после смерти Лейбница среди ученых шел разговор о создании логического универсального языка, подчиняющегося строгим математическим законам. В 1847 году Буль написал важную статью на тему « Математический анализ логики », а в 1854 году развил свои идеи в работе « Исследование законов мышления ».

Буль изобрёл своеобразную алгебру – систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Его именем она теперь и называется : алгебра Буля, или булева алгебра.

Булева алгебра состоит из компонентов : Логические объекты ( выражения ) Операции над логическими объектами Аксиомы и теоремы, регламентирующие эти операции

Логические 2. Предикаты. утверждения

1 Логические утверждения 1. Логические утверждения – это конкретные частные утверждения, заведомо истинные или ложные, иначе говоря, это логические константы. истина -1 Например : 2*2 = 4 ( истина -1) ложь - 0 Волга впадает в Чёрное море. ( ложь - 0)

2 Предикаты – 2. Предикаты – это логические высказывания, значения которых могут меняться в зависимости от входящих в них переменных величин, иначе говоря, это логические переменые. А + В > С А, В, С Например : А + В > С ( принимают значения Истина или Ложь в зависимости от значений А, В, С )

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

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

АВ А٨ВА٨ВА٨ВА٨В И. & ٨. Конъюнкция, определяет соединение двух логических выражений ( высказываний ) с помощью союза И. Обозначается значком & или ٨. Эта операция ставит в соответствие двум простым логическим выражениям новое - сложное, которое будет истинным тогда и только тогда, когда истинны оба исходных ( простых ) логических выражения. Пример : Ученик должен хотеть быть умным и ставить перед собой реальные цели (только одновременное наличие этих двух компонент, делает выражение истинным).

АВ А В ЕСЛИ …, ТО … Импликация связывает два простых логических выражения, из которых первое является условием, а второе - следствием из этого условия. Выражается словами ЕСЛИ …, ТО … Обозначается значком Результатом импликации является ложь тогда и только тогда, когда ( А ) истинно, а следствие ( В ) ложно. Например : Если выучишь материал, то сдашь зачет (высказывание ложно только тогда, когда материал выучен, а зачет не сдан, ведь сдать зачет можно и случайно, например если попался единственный знакомый вопрос или удалось воспользоваться шпаргалкой.

АВ А В АВ, или ˜ Эквивалентность или Равнозначность определяет результат сравнения двух простых логических выражений А и В, обозначается значком или ˜ Результат – новое логическое выражение, которое является истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Пример: Когда в зимний день светит солнце и «кусает» мороз, это значит, что атмосферное давление высокое.

1 1. Инверсия - 2. & ٨ 2. Конъюнкция - & или ٨ 3. ۷ 3. Дизъюнкция – ۷ Импликация – Эквивалентность - Для изменения указанного порядка выполнения логических операций используются круглые скобки. D = ( A ۷ B ٨ C) Например : D = ( A ۷ B ٨ C)

D = A ٨ (B ۷ C) Рассмотрим пример построения таблицы истинности для составного логического выражения. D = A ٨ (B ۷ C) 0 1 А, ВС, Установим число строк и столбцов такой таблицы, что зависит от количества переменных в выражении. При определении числа строк необходимо некоторым образом перебрать все возможные сочетания логических значений 0 и 1 исходных выражений А, В и С, из которых формируется заданное сложное логическое выражение.

Существует закономерность : N 2 n для любого числа N аргументов сложного логического выражения таблица истинности содержит 2 n строк, а также строку заголовка ( шапка таблицы ). М. А, ( В ۷ С ), Количество столбцов таблицы истинности для её построения выбирают равным М. Эти столбцы соответствуют значениям исходных выражений А, В, С, промежуточных результатов А, ( В ۷ С ), а также искомого окончательного результата - значения сложного арифметического выражения А ٨ ( В ۷ С ) А ٨ ( В ۷ С )

АВСА В ۷ С А ٨ (В ۷ С) Построим таблицу сложного логического выражения

1. А ٨ А = А ; А ۷ А = А 1. Отсутствие степеней и коэффициентов ( идемпотентность ): А ٨ А = А ; А ۷ А = А 2.¬(¬ А ) = А 2. Двойное отрицание ( инволюция ): ¬(¬ А ) = А 3. А ۷ ¬ А =1 3. Закон исключения третьего : А ۷ ¬ А =1 ( всегда истина ) 4. А ٨ ¬ А = 0 4. Закон противоречия : А ٨ ¬ А = 0 ( всегда ложь ) 5. А ۷ В = В ۷ А ; А ٨ В = В ٨ А 5. Независимость от перестановки мест ( коммутативность ): А ۷ В = В ۷ А ; А ٨ В = В ٨ А Независимость от порядка выполнения однотипных действий ( ассоциативность ): ( А ۷ В ) ۷ С = А ۷ ( В ۷ С ); ( А ٨ В ) ٨ С = А ٨ ( В ٨ С ). ( А ۷ В ) ۷ С = А ۷ ( В ۷ С ); ( А ٨ В ) ٨ С = А ٨ ( В ٨ С ).

7. 7. Дистрибутивность ( распределение ): Умножения - ( А ۷ В ) ٨ С = ( А ٨ С ) ۷ ( В ٨ С ) ( А ۷ В ) ٨ С = ( А ٨ С ) ۷ ( В ٨ С ) и наоборот : ( А ٨ В ) ۷ ( В ٨ С ) = В ٨ ( А ۷ С ). А ۷ В ٨ С = ( А ۷ В ) ٨ ( А ۷ С ). Сложения - А ۷ В ٨ С = ( А ۷ В ) ٨ ( А ۷ С ) Законы де Моргана : ¬( А ٨ В )= ¬ А ۷ ¬ В а ) Отрицание одновременной истинности : ¬( А ٨ В )= ¬ А ۷ ¬ В ¬ ( А ۷ В ) = ¬ А ٨ ¬ В б ) Отрицание вариантов : ¬ ( А ۷ В ) = ¬ А ٨ ¬ В

АВ ¬ (А۷В) ¬А٨¬ В¬А٨¬ В¬А٨¬ В¬А٨¬ В АВ ¬(А٨В) ¬А۷¬ В¬А۷¬ В¬А۷¬ В¬А۷¬ В ¬ ( А ۷ В ) = ¬ А ٨ ¬ В б ) Отрицание вариантов : ¬ ( А ۷ В ) = ¬ А ٨ ¬ В а) Отрицание одновременной истинности :¬(А٨В)= ¬А۷¬В а) Отрицание одновременной истинности :¬(А٨В)= ¬А۷¬В