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

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

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

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

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

Например : «Два умножить на два равно четырем» - истинное высказывание, ему соответствует значение логической переменной 1: Х=1. « Два умножить на два равно пяти» - ложное высказывание, ему соответствует значение логической переменной 0: У=0.

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

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

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

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

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

Бинарные функции продолжение Штрих Шеффера ( операция И - НЕ ) обозначается 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 Пример : если фигура А квадрат, то фигура А прямоугольник

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

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

Тернарные функции Функция трёх аргументов F m = F m (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)сложение Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

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

Переведем условие задачи на язык алгебры логики. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть : А – « В первой аудитории находится кабинет информатики » В – « Во второй аудитории находится кабинет информатики » Отрицания этих высказываний : А – « В первой аудитории находится кабинет физики » 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 логического элемента подаются четыре пары сигналов, а на выходе получается последовательность из четырёх сигналов, значения которых определяются в соответствии с таблицей истинности операции логического умножения.

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

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

А В &

Пример. По логической схеме получить логическое выражение : & 1 В С А

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

Алгоритм синтеза цифрового устройства Задать словесное описание автомата. Определить количество входов и выходов. Составить таблицу истинности. Записать структурную формулу. Начертить структурную ( функциональную схему ).

Составьте функциональную схему работы цифрового устройства : Для оповещения зрителей на соревнованиях по тяжелой атлетике ( штанга ) используется транспарант « Вес взят правильно ». Транспарант освещается, получив сигнал от троих судей : старшего и двоих помощников. Вес считается взятым правильно, при единодушии всех судей или двоих при условии, что один из судей – старший.

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

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

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

ВходыВыходы ABPY Составим таблицу логических значений для сумматора, где А, В слагаемые, Р и Y перенос и цифра разряда для суммы соответственно: Заметим, что Р это функция, реализующая операцию конъюнкции двух переменных A и В, а Y - отрицание операции эквивалентности: Р = А & В; Y = (A v В ) & ¬( А & В ).

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

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

Самый распространённый тип триггера так называемый RS- триггер (S и R, соответственно, от английских set установка, и reset сброс ). Условное обозначение триггера на рис.

Шифратор и дешифратор. Шифратор и дешифратор являются типовыми узлами ЭВМ. Шифратор ( кодер ) преобразует единичный сигнал на одном из входов в n- разрядный двоичный код.