ОСНОВЫ ЛОГИКИ (Алгебра логики или алгебра высказываний Угринович Стр.123 Практические задания Семакин 7-9 стр.45

ЛОГИКА НАУКА О ФОРМАХ И СПОСОБАХ МЫШЛЕНИЯ Угринович Стр.123

1 этап – формальная логика Основатель – Аристотель ( гг. до н.э. ) Ввёл основные формулы абстрактного мышления

2 этап – математическая логика Н емецкий ученый и философ Лейбниц( ), предпринял попытку логических вычислений.

Джордж Буль – создатель алгебры логики Джордж Буль – английский математик-самоучка ( г) Джордж Буль по праву считается отцом математической логики. Его именем назван раздел математической логики – булева алгебра.

Джордж Буль – создатель алгебры логики Буль изобрел своеобразную алгебру - систему обозначений и правил, применимую ко всевозможным объектам, от чисел до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ), отрицание (НЕ).

Применение алгебры логики для разработки ЭВМ Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключателей схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

Клод Шеннон связал алгебру логики с работой компьютера Клод Шеннон ( г) – американский математик В 1936 году выпускник Мичиганского университета Клод Шеннон, которому был тогда 21 год, сумел ликвидировать разрыв между алгебраической теорией логики и ее практическим приложением

Клод Шеннон связал алгебру логики с работой компьютера Шеннон, имея два диплома бакалавра - по электротехнике и по математике, выполнял обязанности оператора на неуклюжем механическом вычислительном устройстве под названием "дифференциальный анализатор" Постепенно у Шеннона стали вырисовываться контуры устройства компьютера. Если построить электрические цепи в соответствии с принципами булевой алгебры, то они могли бы выражать логические отношения, определять истинность утверждений, а также выполнять сложные вычисления.

Клод Шеннон связал алгебру логики с работой компьютера Электрические схемы, очевидно, были бы гораздо удобнее шестеренок и валиков, щедро смазанных машинным маслом у "дифференциального анализатора". Свои идеи относительно связи между двоичным исчислением, булевой алгеброй и электрическими схемами Шеннон развил в докторской диссертации, опубликованной в 1938 году.

Джон фон Нейман – создатель первой ЭВМ Джон фон Нейман – американский математик

Удивительные способности Неймана Джон фон Нейман родился в 1903 году в семье будапештского банкира и уже в восьмилетнем возрасте владел не только несколькими иностранными языками, но также знал основы высшей математики. Он обладал феноменальной памятью и помнил все, что когда-либо слышал, видел или читал, мог дословно цитировать по памяти большие фрагменты книг, которые читал несколько лет назад.

Появление первых ЭВМ В 1944 году фон Нейман был направлен в качестве консультанта по математическим вопросам в группу разработчиков первой ЭВМ ENIAC. После окончания строительства ENIAC фон Нейман опубликовал отчет "Предварительное обсуждение логической конструкции электронной вычислительной машины". Этот отчет стал исходным пунктом в конструировании новых машин. Сам Нейман занялся разработкой собственной версии вычислительной машины, которую назвал машиной с памятью с прямой адресацией - IAS (Immediate Address Storage).

Открытие фон Неймана Уже во время работ над ENIAC фон Нейман понял, что создание компьютеров с большим количеством переключателей и проводов, которые реализуют тот или иной алгоритм, очень долго и утомительно. И он понял: в памяти машины должны быть не только данные, которые обрабатываются в ходе работы, но также и сама программа. Таким образом, его фундаментальным открытием в области вычислительной техники стала мысль, которая сегодня кажется нам такой естественной: в ходе работы компьютера и программа и обрабатываемые ею данные должны находиться в одном пространстве оперативной памяти.

Применение принципов алгебры логики для создания новой ЭВМ В ходе строительства ENIAC Нейман пришел к выводу, что десятичная арифметика, реализуемая в ENIAC, очень неэффективна. Для каждого десятичного разряда были отведены 10 ламп, и в любой момент времени горела только одна (скажем, если горит седьмая лампа, то в разряде стоит 7, если девятая - 9 и т. д.). В своей машине десятичную арифметику Нейман заменил двоичной.

«Фон-неймановская » машина Все современные компьютеры в главных чертах повторяют архитектуру IAS (вычислительной машины, сконструированной фон Нейманом), которая в специальной литературе сегодня так и именуется - "архитектура фон Неймана", или "фон-неймановская машина". Машина фон Неймана состояла из пяти основных узлов: памяти, арифметико-логического устройства (АЛУ), устройства управления и устройств ввода-вывода (в современных микропроцессорах АЛУ и устройство управления объединены в одном корпусе).

ВЫСКАЗЫВАНИЕ (суждение, утверждение) повествовательное предложение, о котором можно однозначно сказать, что оно истинно или ложно (Пример: Париж – столица Франции) Угринович Стр.123

АЛГЕБРА ЛОГИКИ (высказываний) наука об операциях над высказываниями

Понятия алгебры логики: Логическая переменная Логическая переменная – это простое высказывание, содержащее только одну мысль – Обозначение: латинская буква (А, В, Х …) – Значение: ИСТИНА (1) или ЛОЖЬ (0) Логическая функция Логическая функция (или формула или логическое выражение) – это составное высказывание, которое содержит несколько простых высказываний, соединенных между собой с помощью логических операций – Обозначение: F Логические операции Логические операции – логическое действие (логическое умножение – коньюнкция, логическое сложение – дизъюнкция, отрицание – инверсия, следование – импликация, равенство – эквивалентность) Угринович Стр.125

1.Объясните, почему следующие предложения не являются высказываниями: а)Уходя гасите свет. б)Какого цвета этот дом? в)Посмотрите в окно. 2. Придумай 2 высказывания 3. Придумай сложное высказывание с союзом И

Базовые логические операции НазваниеОбозначениеСоюз в естественном языке Пример А – «Число 10 – четное» В – «Число 10 – отрицательное» Конъюнкция (сonjuncti соединение) (логическое умножение) А ^ B A & B И«Число 10 четное и отрицательное» - ЛОЖЬ Дизъюнкция (disjunctio разделение) (логическое сложение) A v BИЛИ«Число 10 четное или отрицательно» - ИСТИНА Инверсия (inversio – переворачиваю) отрицание) ¬ A Ā НЕ НЕВЕРНО, ЧТО «Число 10 нечетное» – ЛОЖЬ «Число 10 – не отрицательное» - ИСТИНА Импликация (implico тесно связаны) ( логическое следование) А ВЕСЛИ … ТО …; КОГДА …. ТОГДА …. «Если число 10 – четное, то оно отрицательное» - ЛОЖЬ Эквивалентность (логическое равенство) А В … ТОГДА И ТОЛЬКО ТОГДА, КОГДА … «Число 10 – четное тогда и только тогда, когда оно отрицательное» - ЛОЖЬ Угринович Стр

Таблица истинности таблица определяющая значение сложного высказывания при всех возможных значениях простых высказываний

Таблица истинности для конъюнкции (умножение) АВА^ВиА^Ви Вывод: Вывод: Результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны

Таблицаистинностидля дизъюнкции (сложение) Таблица истинности для дизъюнкции (сложение) АВА v В или Вывод Вывод : Результат будет ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным во всех остальных случаях

Таблицаистинностидляинверсии (отрицание) Таблица истинности для инверсии (отрицание) А Ā Вывод Вывод : Результат будет ложным, если исходное высказывание истинно, и наоборот.

Таблицаистинностидля импликации (следование) Таблица истинности для импликации (следование) АВА В Вывод Вывод : Результат будет ложным тогда и только тогда, когда из истинного основания (А) следует ложное следствие (В)

Таблицаистинностидля эквивалентности (равенство) Таблица истинности для эквивалентности (равенство) АВА В Вывод Вывод : Результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится ЛОГИЧЕСКОЕ ВЫРАЖЕНИЕ истина ложь

Порядок выполнения логических операций: Действия в скобках Инверсия (отрицание ) Конъюнкция (умножение И ) Дизъюнкция (сложение ИЛИ ) Импликация (следование ) Эквивалентность (равенство )

Решение задач Семакин ч.2,стр Мая Повторяем

Таблица истинности для конъюнкции (умножение) АВА^ВиА^Ви Вывод: Вывод: Результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны

Таблицаистинностидля дизъюнкции (сложение) Таблица истинности для дизъюнкции (сложение) АВА v В или Вывод Вывод : Результат будет ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным во всех остальных случаях

Таблицаистинностидляинверсии (отрицание) Таблица истинности для инверсии (отрицание) АĀ Вывод Вывод : Результат будет ложным, если исходное высказывание истинно, и наоборот.

Таблицаистинностидля импликации (следование) Таблица истинности для импликации (следование) АВА В Вывод Вывод : Результат будет ложным тогда и только тогда, когда из истинного основания (А) следует ложное следствие (В)

Таблицаистинностидля эквивалентности (равенство) Таблица истинности для эквивалентности (равенство) АВА В Вывод Вывод : Результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

Импликация (Следование) АВА В когда из истины следует ложь Вывод Вывод: Результат будет ложным тогда и только тогда, Пример

Логическая операция ИМЛИКАЦИЯ 4. Операция, выражаемая связками ЕСЛИ..., ТО, ИЗ... СЛЕДУЕТ,... ВЛЕЧЕТ..., называется импликацией (лат. implico тесно связаны) и обозначается знаком ®. Высказывание А ® В ложно тогда и только тогда, когда А истинно, а В ложно. Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: данный четырёхугольник квадрат (А) иоколо данного четырёхугольника можно описать окружность (В). Рассмотрим составное высказывание А ® В, понимаемое как если данный четырёхугольник квадрат, то около него можно описать окружность. Есть три варианта, когда высказывание А ®В истинно: 1.А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность; 1.А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника); 1.A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность. Ложен только один вариант: А истинно и В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

Вопрос 1 1)Операция, соответствующая связке ИЛИ называется………….. 2)Обозначается…… 3)Истинна тогда……

Вопрос 2 1)Операция, соответствующая союзу И называется………….. 2)Обозначается…… 3)Истинна тогда……

Вопрос 3 1)Операция, соответствующая связкамЕСЛИ..., ТО, ИЗ... СЛЕДУЕТ,... ВЛЕЧЕТ..., называется………….. 2)Обозначается…… 3)Ложь тогда……

Вопрос 4 1)Операция, соответствующая связкамтогда и только тогда, "необходимо и достаточно,... равносильно..., называется………….. 2)Обозначается…… 3)Истинна тогда……

6_1 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 1.Марина старше Светы. И Оля старше Светы А= Марина старше Светы; В= Оля старше Светы А И В А^B – это конъюнкция

2. Половина класса изучает английский язык или немецкий А= Одна половина класса изучает английский язык В= Вторая половина – немецкий А ИЛИ В А+B – это дизъюнкция 6_2 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию

6_3 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 3. В кабинете есть учебники. В кабинете есть справочники. А= В кабинете есть учебники В= В кабинете есть справочники А И В А*B – это конъюнкция

6_4 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 4. Слова в этом предложении начинаются на букву Ч. Слова в этом предложении начинаются на букву А. А= Слова в этом предложении начинаются на букву Ч В= Слова в этом предложении начинаются на букву А А ИЛИ В А+B – это дизъюнкция

6_5 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 3. Часть туристов любит чай. Остальные туристы любят молоко А= Часть туристов любит чай В= Остальные туристы любят молоко А И В А*B – это конъюнкция

6_6 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 3. Синий кубик меньше красного. Синий кубик меньше зеленого А= Синий кубик меньше красного В= Синий кубик меньше зеленого А И В А*B – это конъюнкция

6_7 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 3. Х=3, Х>2 А= Х=3. В= Х>2 А И В А*B – это конъюнкция

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

Порядок выполнения логических операций: Действия в скобках Инверсия (отрицание ) Конъюнкция (умножение И ) Дизъюнкция (сложение ИЛИ ) Импликация (следование ) Эквивалентность (равенство )

Правила построения таблиц истинности Установить последовательность выполнения логических операций Найти количество строк в таблице (по формуле 2^n, где n – количество переменных Найти количество столбцов = кол-во переменных + количество операций (действий) Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных Заполнить таблицу по столбцам

Доказать истинность высказывания

Построение таблицы истинности с помощью логических функций в Excel Используются логические функции И ИЛИ НЕ и ЕСЛИ ЗАДАНИЕ 1. Постройте таблицы истинности для дизъюнкции, отрицания. 2. Постройте таблицу истинности для функции

Решение задач Задача 1 Это составное высказывание состоит из простых высказываний: А = «Петя поедет в деревню» В = «Будет хорошая погода» С = «Он пойдет на рыбалку» Записываем высказывание в виде логического выражения, учитывая порядок действий F = A ^ (B C) Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку»

Задача 2 Записать логическое выражение, которое принимает значение true при выполнении указанных условий и значение false в противном случае: каждое из чисел А и В больше 500; хотя бы одно из трех целых чисел делится на 5; каждое из трех заданных целых чисел делится на 3 и оканчивается нулем. A>500 и B>500 АvBvC A&B&CA&B&C

Задача 3 Записать логическое выражение для фразы: Если для солнечной погоды необходимо отсутствие дождя, то для того, чтобы пошел дождь, достаточно, чтобы погода была пасмурной и безветренной. (С Д) (П& В Д)

Задача 4 Вычислить значения логического выражения, если х и у натуральные числа: (1/х>х) and not(1+x 2 >0) or (132

Задача 5 Доказать истинность высказывания Высказывание истинно, так как истинно исходное выражения при любых значениях логических переменных X и Y

Задача 6 Докажите равносильность логических выражений (Отрицание дизъюнкции = конъюнкции отрицаний – правило Моргана) XYX+YNOT(X+Y)NOT(X)NOT(Y)NOT(X) & NOT(Y) Логические выражения равносильны, так как в таблице истинности значения в последних столбцах совпадают

Задания из ЕГЭ Ответы A9 ->2; A10->1; A11->4

Задания из ЕГЭ Ответы 2) Для какого слова истинно высказывание ¬ (Первая буква слова согласная –> (Вторая буква слова гласная \/ Последняя буква слова гласная)) 1) ГОРЕ 2) ПРИВЕТ 3) КРЕСЛО 4) ЗАКОН

Задания из ЕГЭ Ответы 3) Укажите, какое логическое выражение равносильно выражению ¬ (¬A /\ B) \/ ¬C. 1) ¬A \/ B \/ ¬C 2) ¬A \/ ¬B \/ ¬C 3) A \/ ¬B \/ ¬C 4) A \/ B \/ ¬C

Задания из ЕГЭ Ответы Решение: Используя правило де Моргана единственный ответ 4). Укажите, какое логическое выражение равносильно выражению ¬(A \/ ¬ B \/ C) 1)¬A \/ B \/ ¬C2)A /\ ¬B /\ C 3)¬A \/ ¬B \/ ¬C4)¬A /\ B /\ ¬C