ЛОГИКА В ИНФОРМАТИКЕ. ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ

ЛОГИКА ( ОТ ДР. ГРЕЧЕСКОГО ΛΟΓΟΣ МЫСЛЬ ) НАУКА О СПОСОБАХ РАССУЖДЕНИЯ ПРИ ДВИЖЕНИИ К ИСТИНЕ ЛОГИКА ( ОТ ДР. ГРЕЧЕСКОГО ΛΟΓΟΣ МЫСЛЬ ) НАУКА О СПОСОБАХ РАССУЖДЕНИЯ ПРИ ДВИЖЕНИИ К ИСТИНЕ

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

Ответ : Мудрец перестал смеяться потому, что понял, что его голова тоже раскрашена. Этому предшествовали следующие мысли : Допустим головы покрашены, только у двоих других мудрецов, но тогда вскоре один из них поймет, что его голова раскрашена, ведь если бы это было не так, то мудрецу с раскрашенной головой не было бы над чем смеяться. Но мудрецы не перестают смеяться, значит, моё допущение неверно, и моя голова тоже раскрашена. ( Ещё один пример логики, на этот раз женской : Таких, как я, немного : только я... )

ИММАНУИЛ КАНТ ( НЕМ. IMMANUEL KANT [ КЁНИГСБЕРГ ) НЕМЕЦКИЙ ФИЛОСОФ, РОДОНАЧАЛЬНИК НЕМЕЦКОЙ КЛАССИЧЕСКОЙ ФИЛОСОФИИ. НЕМ. [ КЁНИГСБЕРГ ФИЛОСОФ НЕМЕЦКОЙ КЛАССИЧЕСКОЙ ФИЛОСОФИИ НЕМ. [ КЁНИГСБЕРГ ФИЛОСОФ НЕМЕЦКОЙ КЛАССИЧЕСКОЙ ФИЛОСОФИИ Логика - инструмент анализа логических схем.

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

Формы мышления Мышление всегда осуществляется в каких - либо формах. Важными формами мышления являются : Понятия ( например, треугольник, компьютер ). Понятие фиксирует основные, существенные признаки объекта. Высказывания – суждения, выраженные в форме повествовательных предложений. Высказывание может быть либо истинно, либо ложно. Например, сумма углов в треугольнике равна 180 градусам. ( В геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского - ложным ) Простому высказыванию поставим в соответствие логическую переменную Х ( У, Z), которая принимает значение 1, если высказывание истинно, и 0, если высказывание ложно.

Например : «Два умножить на два равно четырем» - истинное высказывание, ему соответствует значение логической переменной 1: Х=1. « Два умножить на два равно пяти» - ложное высказывание, ему соответствует значение логической переменной 0: У=0. Высказывание, состоящее из нескольких простых высказываний, которые связаны с помощью логических союзов «И», «ИЛИ», «ЕСЛИ, ТО» и др., является сложным. Пример: Солнце встало (Х), и птицы запели (У).

Булевы функции : логические выражения и логические операции Каждое сложное высказывание можно выразить в виде формулы, в которую войдут логические переменные ( Х, У и т. д.) и знаки логических операций (, и т. д.). Пример : Х У Любое логическое выражение можно рассматривать как логическую функцию, аргументами которой являются логические переменные. И сама функция, и аргументы могут принимать только два значения : « истина » или « ложь » – 0 или 1. Функции такого вида называются булевыми по имени Джорджа Буля ( ), английского математика и логика ( отца Этель Лилиан Войнич ).

Джордж Буль ( ) английский математик и логик

Булева алгебра ( алгебра ключей ) – теоретическая основа построения телефонных сетей. Телефонистка за работой, фотография предположительно начала XX века

Унарные функции ( операции ) Унарные функции имеют один аргумент. Отрицание - логическая операция инверсии ( логическое " НЕТ "), результатом которой является суждение « противоположное » исходному. Обозначается X или Х, читается не X, удобно представить в виде таблицы : X X X X ЛОЖЬИСТИНА ЛОЖЬ ЛОЖЬ = 0, ИСТИНА = 1 или

Унарные функции ( операции ) продолжение Повторение - тождественная функция, логическое " ДА ". Таблица истинности : Тождественный ноль, тождественная ложь, тождественное " НЕТ ". Таблица истинности : XX X

Унарные функции ( операции ) продолжение Тождественная единица, тождественная истина, тождественное " ДА ". Таблица истинности : Все четыре унарные функции можно представить в одной таблице : X X0 X X

Унарные функции ( операции ) продолжение Пример. Пусть аргументы унарной функции описывают состояние погоды : Х = 1 – светит солнце ( хорошая погода ), а Х = 0 – дождливая погода ( плохая погода ). Пусть результаты унарной функции описывают поведение детей с различными характерами и, поэтому, с разными отношениями к прогулкам : Y = 1 – ребенок гуляет на улице, Y = 0 – ребёнок сидит дома. Тогда таблица примет вид : Погода«домосед»«упрямец»«послушный»«гулёна» плохая сидит дома гуляет сидит дома гуляет хорошая сидит дома гуляет

Бинарные функции Бинарные функции имеют два аргумента Дизъюнкция ( логическое « ИЛИ », логическое сложение ) - логическая операция по своему применению максимально приближённая к союзу « или » в смысле « или то, или это, или оба сразу ». Обозначается X Y ( или X Y), читается X или Y, удобно представить в виде таблицы истинности : XY X Y

Пример : Пусть Х =1, Y=-1, если 1< Х

Бинарные функции продолжение Конъюнкция ( логическое " И ", логическое умножение ) - логическая операция, по своему применению максимально приближённая к союзу " и ". Обозначается X Y ( или X Y, X & Y), читается X и Y, таблица истинности : XY X Y

Пример : Х =1, Y=-1, если 1< Х

Бинарные функции продолжение Штрих Шеффера ( операция И - НЕ ) обозначается X | Y, таблица значений : XYX | Y Штрих Шеффера можно выразить через отрицание и конъюнкцию : X | Y = (X Y) Чтобы это показать, построим таблицу для конъюнкции и инвестируем результат : XY X Y (X Y) Генри Морис Шеффер ( ) американский логик

Бинарные функции продолжение Стрелка Пирса ( операция ИЛИ - НЕ ) означает « ни X, ни Y», обозначается X Y, таблица значений : XYX Y Стрелку Пирса можно выразить через отрицание и дизъюнкцию : X Y = (X Y) Чтобы это показать, построим таблицу для дизъюнкции и инвестируем результат : XY X Y (X Y) Чарльз Сандерс Пирс ( ), американский философ, логик, математик.

Бинарные функции продолжение Импликация (implication ( англ.) - следствие, вывод ) - логическая операция, по своему применению приближенная к союзам « если … то …». Обозначается X Y ( или X Y), таблица истинности : XY X Y Пример : " Житейская " модель импликации : Х начальник. Он может приказать " работай " (1) или сказать " делай что хочешь " (0). Y подчиненный. Он может работать (1) или бездельничать (0). В таком случае импликация послушание подчиненного начальнику. Послушания нет только тогда, когда начальник приказывает работать, а подчиненный бездельничает. Пример : если фигура А квадрат, то фигура А прямоугольник (1,0,0).

Бинарные функции продолжение Эквивалентность логическая операция. Обозначается X Y ( или X Y), означает «X то же самое, что Y», «X эквивалентен Y», «X тогда и только тогда, когда Y». Таблица истинности : XYX Y XY Тождественный ноль, тождественная ложь, тождественное " НЕТ ". Таблица истинности :

Бинарные функции продолжение Тождественная единица, тождественная истина, тождественное " ДА ". Таблица истинности : XY

Все названные бинарные функции можно представить в одной таблице Тождественная единица, тождественная истина, тождественное " ДА ". Таблица истинности : XY0 X Y X | YX Y Есть и другие бинарные операции. Всего бинарных операций - 16.

Тернарные функции Среди логических функций трёх аргументов (X,Y,Z) широко известной является мажоритарная функция, на основе которой в своё время строились комбинационные схемы элементов вычислительной техники. Мажоритарная функция F m принимает значение « истина », в тех случаях, когда два или три её аргумента истинны. Иными словами, таблица истинности функции отражает торжество большинства единиц. Отсюда и название – мажоритарная, т. е. отображающая большинство XYZFmFm

Некоторые свойства логических операций Среди логических функций трёх аргументов (X,Y,Z) широко известной является мажоритарная функция, на основе которой в своё время строились комбинационные схемы элементов вычислительной техники. Мажоритарная функция F m принимает значение « истина », в тех случаях, когда два или три её аргумента истинны. Иными словами, таблица истинности функции отражает торжество большинства единиц. Отсюда и название – мажоритарная, т. е. отображающая большинство XYZFmFm

Некоторые свойства логических операций СВОЙСТВОДЛЯ ЛОГИЧЕСКИХ ОПЕРАЦИЙАНАЛОГИЯ ДЛЯ ОПЕРАЦИЙ С ЧИСЛАМИ коммутативность (переместительный закон) X Y = Y X a + b = b + a ab = ba ассоциативность (сочетательный закон) (X Y) Z= X (Y Z) (a + b) + c = a + (b + c) (ab)c = a(bc) дистрибутивность (распределительный закон) X (Y Z) =(X Y) (X Z) a(b + c) = ab + ac закон двойного отрицания Х=Х -(-a) = a закон исключения третьего Х Х = 1 законы де Моргана (общая инверсия ) (X Y) = Х Y Закон непротиворечия Х Х = 0 Правила исключения констант: 1)Для логического сложения, 2)Для логического умножения. Х 1 = 1, Х 0 = X Х 1 = Х, Х 0 = 0 Раскрытие импликации XY= X Y Раскрытие эквивалентностиXY=(X Y) ( X Y)

Законы легко проверяются с помощью таблиц истинности для обеих частей равенств на всех наборах переменных. Пример : законы де Моргана можно проверить, построив таблицу значений для : (X Y), Х Y, (X Y), Х Y XY (X Y)=XY X Y Х Y XY (X Y)=X|Y X Y Х Y Огастес де Морган ( ), шотландский математик и логик, учитель Ады Лавлейс.

Приоритет логических операций Пример. ¬ А В С D = (( ¬ А ) В ) ( С D). - A B + C D = ((- A) B) + (C D) приоритет логических операций приоритет для операций с числами 1)инверсия 2)конъюнкция 3)дизъюнкция 1)отрицание 2)умножение 3)сложение Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

411 « По крайней мере, в одной из этих аудиторий размещается кабинет информатики » 411 « По крайней мере, в одной из этих аудиторий размещается кабинет информатики » 412 « Кабинет физики находится в другой аудитории »

Решение логических задач с помощью теории булевых функций Условия логической задачи следует записать в виде логической функции. Далее упрощают полученную формулу, что приводит к ответу. Пример : На кафедре биофизики в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На дверях аудиторий студенты - шутники повесили таблички, про которые известно, что либо они обе истинны, либо ложны. На первой аудитории повесили табличку « По крайней мере, в одной из этих аудиторий размещается кабинет информатики », а на второй аудитории – табличку с надписью « Кабинет физики находится в другой аудитории ». Определите, какой кабинет размещается в каждой из аудиторий.

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

Высказывания на табличках : На первой двери – « По крайней мере, в одной из этих аудиторий размещается кабинет информатики », соответствует логическому выражению : Х = А В На второй двери - « Кабинет физики находится в другой аудитории »: У = А Содержащееся в условии задачи утверждение о том, что надписи на табличках одновременно истинные, соответствуют функции эквивалентности : ( Х У ) = 1 Раскроем функцию эквивалентности : ( Х У ) ( Х У ) = 1 Подставим вместо Х и У соответствующие им выражения : (( А В ) А ) ( ( А В ) А ) = 1 Упростим первую и вторую части выражения отдельно : ( А В ) А =( А А ) ( В А ), в соответствии с правилом дистрибутивности. В соответствии с законом непротиворечия : ( А А ) ( В А ) = 0 ( В А ) В соответствии с правилом исключения констант : 0 ( В А ) = ( В А )

В соответствии с законом Де Моргана и законом двойного отрицания : ( ( А В ) А ) = ( А В А ) = ( А А В ) В соответствии с законом непротиворечия : ( А А В ) = (0 В ) = 0 В результате преобразования первого и второго слагаемых получаем : ( В А ) 0 = 1 В соответствии с правилом исключения констант : ( В А ) = 1 Что означает, что справедливы следующие высказывания : Что означает, что справедливы следующие высказывания : В – « Во второй аудитории находится кабинет информатики », В – « Во второй аудитории находится кабинет информатики », А – « В первой аудитории находится кабинет физики ». А – « В первой аудитории находится кабинет физики ».

Логические схемы Компьютеры выполняют программы ( или алгоритмы ). При выполнении программы логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. На вход логического элемента поступают сигналы – аргументы, на выходе появляются сигналы - функции. Преобразование сигнала логическим элементом задаётся фактически таблицей истинности, соответствующей логической функции ( с ними мы уже познакомились ). Любая логическая функция может быть представлена в виде комбинации трёх базовых, поэтому логические схемы компьютера, производящие обработку или хранение информации, могут быть собраны из базовых логических элементов, как из кирпичиков. « Кирпичик » - ВЕНТИЛЬ

В компьютерах первого поколения логические схемы делали на электронных лампах, в компьютерах второго поколения - на транзисторах, сейчас для создания логических схем используют большие интегральные схемы. Базовые логические элементы реализуют три базовые логические операции : Логический элемент « И »( конъюнктор ) – логическое умножение ; Логический элемент « ИЛИ »( дизъюнктор ) – логическое сложение ; Логический элемент « НЕ » ( инвертор ) – инверсию. дизъюнктор X Y конъюнктор X Y инвертор X

Пример : Схемы, выполняющие бинарные функции, изображены в таблице : дизъюнктор X Y конъюнктор X Y штрих Шеффера (X Y) стрелка Пирса (X Y) В компьютерах первого поколения логические схемы делали на электронных лампах, в компьютерах второго поколения - на транзисторах, сейчас для создания логических схем используют большие интегральные схемы.

Рассмотрим подробнее принцип работы логического элемента « И » ( Рис. 1.1): На входы Х 1 и Х 2 логического элемента подаются четыре пары сигналов, а на выходе получается последовательность из четырёх сигналов, значения которых определяются в соответствии с таблицей истинности операции логического умножения. Простейшей моделью логического элемента « И » может быть электрическая схема, состоящая из источника тока, лампочки и двух выключателей. Из схемы видно, что если оба выключателя замкнуты ( на обоих входах 1), по цепи идёт ток и лампочка горит ( на выходе 1). Если хотя бы один выключатель разомкнут ( на одном из входов 0), то тока нет и лампочка не горит ( на выходе 0)

Устимкина Л. И., ББСОШ 1 40 А В АВ И ИЛИ НЕ Логические схемы

В третьем устройстве в качестве переключателя используются автоматический ключ. Когда тока в цепи ключа нет, пластинка замыкает контакты и лампочка горит. Если на ключ подать напряжение, то вследствие явления электромагнитной индукции пластинка прижимается к электромагниту и цепь размыкается. Лампочка не горит.

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

Пример. Построить логическую схему соответствующую логическому выражению AvB A.

Решение : AvB A = Av(B A). Сначала строим конъюнктор B A. Выход конъюнктора и вход А - входы для следующего дизъюнктора :

Решение : Первым ( слева ) стоит конъюнктор B С. Выход конъюнктора и А - входы для следующего дизъюнктора Av(B С ). Последним стоит инвентор. Получаем : (AvB C).

Пример логической схемы персонального компьютера, разработанного А. Ф. Волковым из г. Днепродзержинска в 1985 г. и печатная плата машины Pentagon SL, реализованная на базе ПЛИС FPGA EP2C8Q208C8N. pentagon.nedopc.com

Этапы конструирования логического устройства. Конструирование логического устройства состоит из следующих этапов : 1. Построение таблицы истинности по заданным условиям работы проектируемого узла ( т. е. по соответствию его входных и выходных сигналов ). 2. Конструирование логической функции данного узла по таблице истинности, ее преобразование ( упрощение ), если это возможно и необходимо. 3. Составление функциональной схемы проектируемого узла по формуле логической функции.

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