Лепшова Екатерина Сергеевна Лекция 5: Алгебра логики. Логические основы работы компьютера 10 2 – класс Тверской лицей Тверской Государственный технический Университет Лепшова Екатерина Сергеевна

Аристотель ( гг. до н.э.) Готфрид Вильгельм Лейбниц ( гг.) Джордж Буль ( гг.) Логика это наука о формах и способах мышления. Дальнейшее изучение курса информатики связано с трудами трёх великих учёных. Они являются основоположниками серьёзной науки, которая называется ЛОГИКА. Назовите их имена?

Понятие форма мышления, которая выделяет существенные признаки предмета (класса предметов), позволяющие отличать его от других. Примеры: проливной дождь, круглый шар, новый компьютер. Высказывание (суждение/утверждение) это формулировка своего понимания окр. мира. Высказывание является повествовательным предложением, в котором что-то утверждается или отрицается. Поэтому, высказывание может быть истинным или ложным. Истинное высказывание - правильно отражает реальную действительность. Ложное - противоречит действительности. Примеры: «У прямоугольника все углы прямые» (Истинное высказывание). «Компьютер был изобретен в середине XIX века (Ложное высказывание). Умозаключение форма мышления, с помощью кот. из одного или нескольких суждений м. б. получено новое суждение. Пример: Из высказывания: «Равнобедренный треугольник, у кот. все углы равны» м. путём умозаключений получить другое высказывание «Этот треугольник равносторонний». ( гг. до н.э.) Аристотель - основатель Формальной логики. Описал основные формы абстрактного мышления: понятие, высказывание, умозаключение.

Готфрид ВильгельмЛейбниц немецкий учёный и философ - основатель Математической логики. Готфрид Вильгельм Лейбниц немецкий учёный и философ - основатель Математической логики. Он же является создателем одной из первых механических вычислительных машин, которая могла складывать, вычитать, умножать, делить и извлекать квадратные корни. Ступенчатый вычислитель Лейбница - прототип современных компьютеров. Английский математик Джордж Буль - основатель Алгебры логики. В своих трудах описал алфавит, орфографию и грамматику для математической логики.

Высказывание - повествовательное предложение, о котором можно сказать, истинно оно или ложно. Т.е. высказывание может принимать одно из двух значений – истина (1) или ложь (0). Задание для тренировки (устно): Какие из предложений являются высказываниями? Определите их истинность. ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ = Без труда не вытащишь и рыбку из пруда. 10. Сложите числа 2 и Некоторые медведи живут на севере. 12. Все медведи бурые. 13. Чему равно расстояние от Москвы до Ленинграда? 1. Какой длины эта лента? 2. Прослушайте сообщение. 3. Делайте утреннюю зарядку! 4. Назовите устройство ввода информации. 5. Кто отсутствует? 6. Париж столица Англии. 7. Число 11 является простым. Тема «Логические основы работы компьютера» Цели: - познакомить учащихся с основными формами мышления; - сформировать понятия: логическая переменная, логическая операция План урока: 1. Изложение нового материала 2. Решение задач

ВЫСКАЗЫВАНИЯ Простые (содержат только одну простую мысль) «Петров – врач» «Петров – шахматист» Составные (содержат несколько простых высказываний соединённых логическими связками: «и», «или», «не», «если …то», «тогда и только тогда») «Петров - врач и шахматист» «Петров – не врач и не шахматист» В алгебре простые высказывания обозначаются буквами латинского алфавита и наз. логическими переменными. Обозначив А = «Петров – врач», В = «Петров – шахматист», получим логические выражения (функции): F(A,B) = А и В ( «Петров - врач и шахматист») F(A,B) = не А и не В («Петров – не врач и не шахматист») Значение логической функции можно определить с помощью спец. таблицы – таблицы истинности таблицы истинности, в кот. перечисляются все комбинации значений лог. переменных, входящих в выражение, и определяются соотв. значения лог. функции. АВF (A,B)=А и В

ТАБЛИЦЫ ИСТИННОСТИ Таблица истинности – это таблица, с помощью которой определяются значения логических выражений. ПОРЯДОК ВЫПОЛНЕНИЯ ОПЕРАЦИЙ В ЛОГИЧЕСКИХ ВЫРАЖЕНИЯХ действия в скобках; инверсия (¬), конъюнкция (^), дизъюнкция (v), импликация (), эквивалентность().

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ 1. Отрицание (инверсия) «НЕ» ¬ от лат. inversio переворачиваю, А¬ А Логич. сложение ( дизьюнкция) «ИЛИ» +, v от лат. disjunctio - различаю АВА+В Логич. умножение ( конъюнкция) «И», х, ^ & от лат. conjunctio – соединяю АВА В Из таблицы видно: Инверсия лог. переменной истинна, если сама переменная ложна, и наоборот, … Из таблицы видно : Дизьюнкция ложна, если ложны обе переменные, и истинна - во всех остальных случаях. Из таблицы видно : Конъюнкция истинна, если истинны обе переменные, и ложна - во всех остальных случаях.

4. Логическое следование ( импликация) «ЕСЛИ … ТО» от лат. implicatio тесно связываю, АВАВ Из таблицы видно : Импликация ложна, если из истины следует ложь, и истинна - во всех остальных случаях. 5. Логическое равенство ( эквивалентность/равнозначность) «ТОГДА И ТОЛЬКО ТОГДА, КОГДА …» « НЕОБХОДИМО И ДОСТАТОЧНО » от лат. equivalents равноценное АВАВ Из таблицы видно : Эквивалентность истинна, если обе переменные одновременно либо истинны, либо ложны. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Задания для закрепления пройденного материала: Упражнение 1: Запишите следующие высказывания в виде логических выражений: – Число 17 нечетное и двузначное. – Неверно, что корова - хищное животное. – Если число делится на 2, то оно - четное. – Если Маша - сестра Саши, то Саша - брат Маши. – Водительские права можно получить тогда и только тогда, когда тебе исполнится 18 лет. – Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку

Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку». Проанализируем составное высказывание. Оно состоит из следующих высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдет на рыбалку». Обозначим их через логические переменные: А = Петя поедет в деревню; В = Будет хорошая погода; С = Он пойдет на рыбалку. 2. Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки: F = A&(BC) Пример:

2: Упражнение 2: Есть два простых высказывания: А - «Число 10 - четное»; В - «Волк - травоядное животное». Составьте из них все возможные составные высказывания и определите их истинность. Упражнение 3: Найдите значения логических выражений: l) F = (0 v 0) v (l v l) 2) F = ( l v l )v(l v0) 3) F = (0&0)&(1&1) 4) F = 1&(1 v 1) v (¬0&1) 5) F = (¬1 v 1)&(1 v¬l)&( ¬l v 0) Задания для закрепления пройденного материала: = 1 = 0 = 1 = 0

ТАБЛИЦА ИСТИННОСТИ – таблица, которая выражает соответствие между всевозможными наборами значений переменных и значениями формулы. выполнимой. Если в таблице истинности формула хотя бы один раз принимает значение 1, то она является выполнимой. Построение таблиц истинности

Алгоритм построения ТИ для логической формулы: 1)Определить количество строк и столбцов в ТИ 2)Заполняем заголовок таблицы (названия столбцов): сначала вписываем все простые высказывания, затем определяем порядок операций ( ) и вписываем соответственно составные высказывания 3)Заполняем первые столбцы ТИ всевозможными значениями для простых высказываний 4)Заполняем остальные столбцы, выполняя логические операции

Количество строк в таблице истинности формулы определяется по формуле 2 N + 1, где N – количество простых высказываний в формуле Например: 1)Для формулы количество строк в ТИ будет равно =8+1=9 1)Для формулы количество строк в ТИ будет равно =4+1=5

Количество столбцов в таблице истинности формулы определяется по формуле N + oп, где N – количество простых высказываний в формуле, оп – количество логических операций в формуле Например: 1)Для формулы количество столбцов в ТИ будет равно 3+4=7 2)Для формулы количество строк в ТИ будет равно 2+7=9

Алгоритм построения ТИ для формулы количество строк – 9, количество столбцов - 7

Алгоритм построения ТИ для формулы a b c n m b b

Алгоритм построения ТИ для формулы a b c n m b b

a b c b b Алгоритм построения ТИ для формулы n m

a b c b b Алгоритм построения ТИ для формулы n m

a b c b b Алгоритм построения ТИ для формулы n m

a b c b b Алгоритм построения ТИ для формулы n m

a b c b b n m

a b c b b Алгоритм построения ТИ для формулы n m

Упражнение: Построить ТИ следующих формул 1) 2) 3) 4)