Составление таблиц истинности. Составление функциональных схем по логическим формулам

Практическая работа №3

Составление таблиц истинности. Составление функциональных схем по логическим формулам

Цель: формирование навыков и умений работать с основными логическими операциями, базовыми логическими элементами (И, И-НЕ, ИЛИ, ИЛИ-НЕ, исключающее ИЛИ), построения таблиц истинности по высказываниям; закрепить методы построения логических схем на основе логических элементов.

Порядок выполнения работы

1. Изучить общие понятия, лежащие в основе алгебры логики.
2. Освоить правила составления таблиц истинности логических выражений.
3. Получить навыки составления функциональные схемы по логическим выражениям.

Теоретическая часть

Логика – одна из древнейших наук. Ее основателем считается древнегреческий мыслитель Аристотель (384 – 322гг. до н. э.), который первым систематизировал формы и правила мышления, обстоятельно исследовал категории понятие и суждение, подробно разработал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления. Он подвергал анализу человеческое мышление, его формы – понятие, суждение, умозаключение, и рассмотрел со стороны строения, структуры. Логика Аристотеля носит название формальной логики. Это название происходит из принципа: правильность рассуждения определяется только его логической формой или структурой и не зависит от конкретного содержания входящих в него высказываний.

Продолжение развития логики связано математической логикой. Основоположником математической логики считается великий математик и философ Готфрид Вильгельм Лейбниц (1646-1716). Он попытался построить первые логические исчисления: арифметические и буквенно-алгебраические. Лейбниц заложил идейный фундамент математической логики, а над практической реализацией этих идей работали и работают многие учёные.

Джордж Буль (1815-1864, ирландский математик и логик) – основоположник математической логики. В 1847 г. Джордж  Буль в работе «Математический анализ логики» изложил основы булевой алгебры.   Разработал алфавит, орфографию и грамматику.

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

Развитие идей Буля привело  к созданию современной математической логики, которая включает в себя алгебру множеств, алгебру высказываний, алгебру релейных схем (реле – это  переключатель в электрических  схемах), без которых было бы невозможным  проектирование и программирование вычислительных машин. Именно булева алгебра  лежит в основе работы компьютера.

 В отличие от обычной логики, в ней символами обозначаются не числа, а высказывания. Алгебра логики (булева алгебра) изучает высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.

Создание алгебры логики представляло собой попытку решать традиционные логические задачи алгебраическими методами. С появлением теории множеств (70-е гг. 19 в.), поглотившей часть первоначального предмета алгебры логики, и дальнейшим развитием математической логики (последняя четверть 19 в. – 1-я половина 20 в.) предмет алгебр логики значительно изменился. Основным предметом алгебры логики стали высказывания. Под высказыванием понимается имеющее смысл языковое выражение, относительно которого можно утверждать, что оно либо истинно, либо ложно.

Пример 1.

• «5 есть простое число». Это высказыванием является истинным.

• «4 + х = 6». Это уравнение не является высказыванием. Однако, придавая переменной х определенное числовое значение, будет высказывание.

• «роза – цветок». Это высказывание является истинным.

• «все углы – прямые». Это высказывание является ложным.

• «3 + 5 = 9». Это высказывание является ложным.

Высказывание считается простым, если никакая его часть не является суждением. Сложное высказывание характеризуется тем, что оно образованно из нескольких высказываний с помощью определенных способов соединения.

Пример 2.

• «Париж – столица Франции». Это высказывание простое.

• «Неверно, что Париж – столица Англии». Это высказывание сложное.

Частные высказывания выражают конкретные факты. Общие высказывания характеризуют свойства групп объектов или явлений.

Пример 3.

• «Луна - спутник Земли». Это частное высказывание.

• «Всякий человек – млекопитающее». Это общее высказывание.

Рассуждение - это цепочка взаимосвязанных высказываний, фактов и общих положений, полученных из других высказываний по определенным правилам вывода.

Пример 4.

• «Если треугольник равносторонний, то у него все углы равны между собой».
• «Если король под шахом и ему некуда ходить, то – мат».

Умозаключение – прием мышления, посредством которого из исходного знания получается новое знание; из одного или нескольких истинных высказываний, называемых предпосылками, по определенным правилам вывода можно получить заключение.

Пример 5.

«Все металлы – простые  вещества». «Литий – металл». Следовательно  «Литий – простое вещество».

Любое правило вывода умозаключений  состоит из двух высказываний (простых  или сложных). Одно из них называется предпосылкой или условием, а второе – следствием, заключением или выводом.

Пример 6.

«Если треугольник равносторонний, то у него все углы 60 градусов».

Высказывание «У него все  углы равны 60 градусов» – это  заключение, а высказывание «Треугольник равносторонний» – это предпосылка.

Существуют умозаключения, осуществляемые по схемам аналогии, индукции и дедукции.

Умозаключение по аналогии – это правило полученное из рассмотрения какого-либо объекта, переносимое на менее изученный, сходный по существенным свойствам и качествам объекта.

Пример 7.

Из высказывания «Солнечная система – это планеты, вращающиеся  по орбитам, в центре которых находится Солнце» можно получить умозаключение по аналогии: «Атом – это электроны, вращающиеся по орбитам, в центре которых находится ядро».

Индукция – это правило вывода умозаключений при переходе от частных высказываний к общим.

Пример 8.

Высказывания: «кошки имеют  хвост», «собаки имеют хвост», «обезьяны  имеют хвост», «кошки, собаки, обезьяна – млекопитающие». Следовательно, «все млекопитающие имеют хвост». Это умозаключение ложно.

Индуктивный вывод умозаключений  позволяет формулировать различные  гипотезы, догадки, но иногда он может приводить и к ошибочным умозаключениям.

Дедукция – это правило вывода умозаключений при переходе от общих суждений к частным.

Пример 9.

«Умные люди не делают ошибки». «Я – умный человек». Следовательно: «Я не делаю ошибок».

В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывания можно представить некоторой переменной величиной, значением которой может быть только «0» или «1». Если высказывание истинно, то его значение равно «1», если ложно, то равно «0».

Из уже заданных простых  высказываний можно строить более  сложные высказывания, используя частицу «не», а также союзы «и», «или», «если..., то...», «тогда и только тогда, когда» и т.п..

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

 

Пример 10.

• Из высказываний «х > 2», «х < 3» при помощи связки «и» можно получить высказывание «x > 2 и х < 3»;

• из высказываний «у > 10», «х < 3» при помощи связки «или» можно получить высказывание «у > 10 или х < 3»;

• из высказываний «х > 2», «у < 3» при помощи связки «если..., то...» можно получить высказывание «если x > 2, то у < 3».

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

Логическая переменная – это простое высказывание, содержащее только одну мысль. Её символическое обозначение – латинская буква (например, A, B, X, Y и т.д.) Значением логической переменной могут быть только константы ИСТИНА и ЛОЖЬ (1 и 0).

Логическая функция – составное высказывание, которое содержит несколько простых мыслей, соединённых между собой с помощью логических операций. Её символическое обозначение – F (A, B…)

 Логическая операция – логическое действие.

С помощью логических переменных и символов логических операций любое  высказывание можно формализовать, то есть заменить логической функцией.

Например: Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдёт на рыбалку».

Проанализируем составное  высказывание и обозначим простые  высказывания  через логические переменные:

А = Петя поедет в деревню;

В = Будет хорошая погода;

С = Он пойдет на рыбалку.

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

В алгебре логики логические операции чаще всего описываются  при помощи таблиц истинности.

Таблица истинности - это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию и значениями функции.

Таблицы истинности применяются  для:

- вычисления истинности  сложных высказываний;

- установления эквивалентности  высказываний;

- определения тождественно-истинных (тавтологий) и тождественно-ложных высказываний.

Алгоритм построения таблицы истинности:

1. подсчитать количество логических переменных «n» в составном высказывании;
2. определить число строк в таблице, которое равно m=2ⁿ;
3. подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных  плюс количество   операций;
4. ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций   с учётом скобок и приоритетов;
5. заполнить столбцы входных переменных  наборами значений;
6. провести заполнение таблицы истинности по столбцам, выполняя логические операции  в соответствии  с установленной в п.4 последовательностью.

Базовые логические операции

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

А	В	С=АÙВ
0	0	0
0	1	0
1	0	0
1	1	1

Обозначается: А^В = А*В = А и В = А&В = А В = А ∙ В

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

 

Пример. Высказывания А= «Москва – столица России» и  
В= «Рим – столица Италии». Сложное высказывание А ∧ В (А & В) истинно, так как истинны оба высказывания.

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

Обозначения: АÚ В = А или В = А+В

А	В	С=А Ú В
0	0	0
0	1	1
1	0	1
1	1	1

 

Пример. Высказывания А = «2 + 3 = 5» и В = «3+3=5». Сложное высказывание: А ∨ В (А + В) истинно, так как истинно высказывание А.

 

 

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

А	С =
0	1
1	0

Обозначается не А = ¬А = ù А = или ~ A и часто читается: «отрицание А», «не А» или «А с чертой»: 

Пример. Высказывание А= «Киев – столица Франции», тогда сложное высказывание НЕ А означает: не верно, что А, т.е. не верно, что «Киев –столица Франции».

Приведем ещё  примеры отрицания:

1) Высказывание «Земля вращается вокруг Солнца» истинно. Высказывание «Земля не вращается вокруг Солнца» ложно.

2) Высказывание «4 –  не простое число» истинно.  Высказывание «4 – простое  число» ложно.