Бабкина Наталья Анатольевна, преподаватель
Основы алгебры-логики
Цели- задачи: Знать: Основные понятия алгебры логики. Основные операции алгебры логики. Понятие таблицы истинности. Алгоритм составления таблицы истинности.
План лекции: 1.Понятие алгебры-логики. История возникновения. 2. Логические операции. 3.Логические выражения и функции 4.Таблицы истинности.
1.Понятие алгебры-логики. История возникновения.
Принятие решения- это в конечном счёте всегда прерогатива человека.
В компьютере надо смоделировать процесс рассуждений, которые проводит человек.
Первым, кто предпринял удачную попытку построить модель человеческих рассуждений, был, по мнению историков науки, древнегреческий учёный Аристотель.
Именно он первым сформулировал первые законы рассуждений, заложив основы новой науки, названной им ЛОГИКОЙ. Логика – наука, изучающая законы и формы мышления
После Аристотеля вклад в эту науку вносили психологи, философы, лингвисты и математики. У этой науки появились разные направления исследования. Одним из направлений выделилась формальная или математическая логика.
Модели , создаваемые в результате исследований внутри логики, стали называть моделями искусственного интеллекта.
I -этапом можно считать учения Аристотеля . II-этапом обычно считают внедрение математической логики. Основатель – немецкий ученый и философ Лейбниц (1642 – 1716), предпринял попытку логических вычислений.
Алгебра логика– это математический аппарат, с помощью которого записывают (кодируют), упрощают, вычисляют и преобразовывают логические высказывания. Высказывание – повествовательное предложение, о котором можно сказать, истинно оно или ложно.
III этапом - математическая логика (булева алгебра- алгебра логики). Основатель - английский математик Джордж Буль (1815 – 1864), ввел алфавит, орфографию и грамматику для математической логики.
Августус Уильям Чарлз де Морган Стенли Сандерс (1806-1801) Джевонс Пирс (1835-1882) (1839-1914)
Андрей Андрей Андреевич Николаевич Марков Колмогоров (1903-1979) (1903-1978)
Прошло сто лет со времени создания алгебры –логики Дж.Булем, прежде чем в 1938 году математик и инженер Клод Шеннон применил её для описания самых разнообразных процессов, в том числе функционирования релейно- контактных схем и электронно- ламповых схем.
Высказывание может принимать только одно из двух логических значений – истинно (1) или ложь (0). Поэтому принципы логики применяются в проектировании цифровых устройств Примеры высказываний: Земля – планета Солнечной системы (истинное высказывание). 3+6>10 (ложное высказывание).
Умозаключение-это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение, знание или вывод.
Пример. Дано высказывание: «Все углы равнобедренного треугольника равны». Получить высказывание «Этот треугольник равносторонний» путем умозаключений. Пусть основанием треугольника является сторона с. Тогда a=b. Так как в треугольнике все углы равны, следовательно, основанием может быть любая другая сторона, например а. Тогда b=c. Следовательно a=b=c. Треугольник равносторонний.
Высказывания бывают простые и сложные. Простое высказывание (логическая переменная) содержит только одну простую мысль. Логические переменные обычно обозначаются буквами латинского алфавита: A, B, C, D… Например, А= {Квадрат – это ромб}.
Сложное высказывание (логическая функция) содержит несколько простых мыслей, соединенных между собой с помощью логических операций. Например, F (A, B,) = {Лил дождь, и дул холодный ветер }. А В
2. Логические операции
Употребляемые в обычной речи связки «И», «ИЛИ», «НЕ», «Если…, то», «Тогда и только тогда, когда…» и т. д. позволяют из уже заданных высказываний строить новые сложные высказывания.
Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как логических операций над высказываниями.
Логическая операция- это способ построения сложного высказывания из данных высказываний, при котором значение истинности сложного высказывания полностью определяется значениями истинности исходных высказываний.
Для обозначения истинности, как правило, используются символы «И» и «1», а для обозначения ложности- символы «Л» и «0».
Отрицание (инверсия), от лат. Inversio- переворачивают: соответствует частице НЕ, словосочетанию НЕВЕРНО, ЧТО; обозначение: не А, A, ,¬ А
Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна. Пример: ф={На улице идет снег}. ={Неверно, что на улице идет снег} ={На улице не идет снег};
Логическое сложение (дизъюнкция), от лат. disjunctio -различаю: Соответствует союзу ИЛИ; Обозначение: 1,+, или, or, V; Дизъюнкция ложна тогда и только тогда, когда оба высказывания ложны. Пример: F={На улице светит солнце или дует сильный ветер};
Логическое умножение (конъюнкция), от лат. conjunctio – связываю: Соответствует союзу И (в естественном языке: и А, и В как А, так и В А вместе с В А, несмотря на В А, в то время как В); Обозначение: х, , &, и, ^, and;
Конъюнкция истинна тогда и только тогда, когда оба высказывания истинны. Пример: F={На улице светит солнце и дует сильный ветер};
Любое сложное высказывание можно записать с помощью основных логических высказываний. И, ИЛИ, НЕ. С помощью логических схем И, ИЛИ, НЕ можно реализовать любую логическую функцию, описывающую работу различных цифровых устройств и их блоков.
Импликация (логическое следование), от лат. implicatio – тесно связываю: Соответствует речевому обороту ЕСЛИ…ТО (в естественном языке: если А, то В В, если А В необходимо для А А необходимо для В А только тогда, когда В В только тогда, когда А Все А есть В; Обозначение: ⇒ ,
Импликация истинна всегда, за исключением случая, когда А истинно, а В ложно. Пример: Если идет дождь, то земля мокрая. АВ F=A B
Эквивалентность (равнозначность), от лат. equivalens – равноценное: соответствует речевым оборотам ЭКВИВАЛЕНТНО: необходимо и достаточно для Эквивалентность истинна тогда и только тогда, когда оба высказывания одновременно либо истинны, либо ложны. Пример: Я пойду гулять тогда и только тогда, когда выучу все уроки.
3. Логические выражения
Логическое выражение (логическая форма)- это выражение, содержащее одну или несколько переменных, соединённых знаками логических операций и скобками и превращающихся в высказывания при подстановке вместо этих перемаенных простых суждений Выражения алгебры логики также называют формулами.
Можно определить и логические функции от логических переменных. Логическая функция- это функция, определённая на множестве истинностных значений(истина, ложь).
Реальную задачу мы получаем, как правило, в виде текста на естественном языке. Прежде , чем приступить к её решению, необходимо выделить простые высказывания, отношения (связи) между ними и перевести их на язык формул (формализовать условие задачи, определить формулу сложного высказывания).
В случае простого высказывания всегда допустимо договориться о том, считать его истинным или ложным. Сложное высказывание также является истинным или ложным, но это значение вычисляется. Вычисление производится по форме сложного высказывания в соответствии с таблицами истинности входящих в него логических операций.
Пример. Е=Ваш приезд не является ни необходимым, ни желательным. Составляющие простые высказывания: А=Ваш приезд необходим. В=Ваш приезд желателен. Форма сложного высказывания: Å = À∧Â
4. Таблицы истинности
Значение логической функции можно определить с помощью специальной таблицы (таблицы истинности). Таблица истинности - таблица, в которой перечислены все возможные значения входящих логических переменных и соответствующие им значения функции.
Количество строк (q) в таблице истинности можно вычислить по формуле q=2n.(1) n-количество переменных.
Для составления таблицы необходимо: Выяснить количество строк в таблице по формуле 1. Выяснить количество столбцов = количество переменных +количество логических операций. Установить последовательность выполнения логических операций. Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных. Заполнить таблицу истинности по столбцам.
Например, A B F (A, B) 00 0 01 1 10 0 11 0 A и B – логические переменные, n=2 F – логическая функция
Таблицы истинности основных операций Инверсия Дизъюнкция АA AB F 000 01 011 А 10 101 111
Конъюнкция Импликация ABF АB F 1 0 00 00 1 0 0 10 01 1 1 00 10 1 11 11 Эквивалентность A BF 0 01 0 10 1 00 1 11
Задание 1. Записать в тетради тему. 2. Записать определения терминов , выделенных курсивом( для операций- обязательно обозначения). 3. Записать к каждой операции- таблицу истинности. 4. Записать и выучить алгоритм создания таблицы истинности. 5. Выучить определения, записанные в тетради.
Search
