Логика

Логика – наука о законах и формах мышления.
Слово «логика» произошло от древнегреческого logos, что означает «слово, мысль, понятие, рассуждение, закон».
Основные формы мышления: понятие, высказывание, умозаключение.
Понятие – это форма мышления, которая выделяет существенные признаки предмета или класса предметов, позволяющие отличать их от других («Вот стул на нем сидят, вот стол – за ним едят.»).
Высказывание – это повествовательное предложение, о котором можно сказать, истинно оно или ложно.
Земля – планета солнечной системы. 3+5=19
Умозаключение – это форма мышления, с помощью которой из одного или несколько суждений может быть получено новое суждение (вывод). ( Доказательство теорем в алгебре).
Английский математик Джордж Буль (1815-1864) изобрел своеобразную алгебру – систему обозначений и правил, применимую к всевозможным объектам, в частности к высказываниям. Эта алгебра называется его именем – алгебра Буля или булева алгебра.
Логическая переменная – это простое высказывание (содержит одну мысль), значение которой 0 (ложь, false) или 1 (истина, true), обозначается латинскими буквами.
Логическая функция – составное высказывание, полученное из простых высказываний, соединенных между собой с помощью логических операций.

Логические операции.
Логические операции над высказываниями выполняются на основе законов и правил булевой алгебры.
Логическое умножение КОНЪЮНКЦИЯ (∧,&) определяет соединение логических выражений с помощью союза И.
Например: 1) А – “Х>10”; В – “Х< 30”; А и В - “10
2) А – “Компьютер предназначен для обработки информации”
В – “Компьютер предназначен для хранения информации”
А и В – “Компьютер предназначен для обработки и хранения информации”
3) Иванов посещает факультатив по математике и по физике.
Сложное высказывание А и В принимает значение - истина, когда оба высказывания принимают значение - истина.
Логическое сложение ДИЗЪЮНКЦИЯ (∨) определяет соединение логических выражений с помощью союза ИЛИ.
Например: В библиотеке есть книги Беляева А.Р. или книги других фантастов. Х≥0.
Иванов участвует в олимпиаде по математике или по физике.
Сложное высказывание А или В принимает значение - истина, когда хотя бы одно из высказываний принимает значение - истина.
Отрицание ИНВЕРСИЯ - НЕ (¬ ) изменяет значение логического высказывания на противоположное.
Например: 1) А – “а – простое числи”; не А – “неверно, что а – простое число.»

Логические операции.
Импликация (логическое следование) (→) соответствует связке « если …, то …»
Если А, то В, В необходимо для А, А достаточно для В, В тогда, когда А
Импликация истинна всегда, за исключением случая, когда А истинно, а В ложно.
Пример: Если идет дождь, то земля сухая. (ложь)
А - “х делится на 9”
В - “х делится на 3”
А → В - “если число х делится на 9, то оно делится на 3” (истина)
Эквивалентность(равнозначность) (⇔, = ) соответствует связке «тогда и только тогда, когда..». А тогда и только тогда, когда В
Результат эквивалентности будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны.
Исключающая дизъюнкция «либо…, либо» ⊕, (неэквивалентность) А ⊕В.
Результат будет истинным, когда одно из исходных выражений истинно, а другое ложно.
Пример: Пан или пропал.

Построение таблиц истинности.
Таблица истинности – таблица, определяющая значение сложного высказывания при всех возможных значениях простых высказываниях.
Для составления таблицы надо:
определить число переменных;
выяснить количество строк в таблице (вычисляется как 2n, где n – количество переменных);
выяснить количество столбцов = количеств переменных + количество логических операций;
установить последовательность выполнения логических операций;
записать логические операции в таблицу истинности и определить для каждого значение;
Порядок выполнения логических операций:
операция в скобках;
отрицание;
логическое умножение;
логическое сложение;
импликация;
эквивалентность.

Составьте по булевому выражению F=(A∨В)∧¬C таблицу истинности:
_ _ _
Самостоятельно: 1) F=A∨(В∧C); 2) F=A∧(В∨∧C); 3) F=(A∧В) ∨C.

Законы алгебры логики.
Если логическое выражение содержит большое число операций, то составлять для него таблицу истинности достаточно сложно. В таких случаях формулы надо привести к нормальной форме. Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации, двойного отрицания, знаки отрицания находятся только при логических переменных. Для приведения формулы к нормальной форме используют законы логики и правила преобразований.
Тождества.

Законы алгебры логики.
Переместительный закон
А + В = В + А А & В = В & А
Сочетательный закон
(А + В) + C =А + (В + C) (А& В)& С =А& (В&С)
Распределительный закон
(А + В)&C =А&С+ В&C) дистрибутивность конъюнкции относительно дизъюнкции – аналог раскрытия скобок в алгебре
А& В +С =(А + С)& (В + С) дистрибутивность дизъюнкции относительно конъюнкции – «чудо» логики, в алгебре аналога нет.
Закон де Моргана (закон отрицания)
____ _ _ _____ _ _
А + В = А& В А & В = А + В
Доказать на уроке, используя таблицы истинности.
__ __
А → В = В → А = А + В
_ _ _ _
А ↔ В = А& В + А & В = ( А + В) &( А + В)

Задания:
1) Записать формулу, упростить:
А или (не А и В)
А и (не А или В)
(А или В) и (не В или А) и (не С или В)
(1 или (А или В)) или ((А или С) и 1)
Решение:
__ __
А + (А & B) = (А + А)&(А + В) = 1& (А + В) = А +В;
__ __
А & (А + В) = А&А + А&В = 0 + А&В = А&В;
__ __ __ __ __
(А + В)&( В + А)&(С + В) =(А&В +А&А +В&В + В&А)&(С +В) =
__ __ __ __ __
(А&В + А + 0 + В&А)& (С +В) = А&(В + 1 + В)& (С +В) =А&(С +В);
(1 + (А + В)) + (( А + С)&1) = 1 + (А + С) =1.
2) Доказать, используя таблицы истинности, второй распределительный закон А& В +С =(А + С)& (В + С).

Логические схемы.
Над возможностями применения логики в технике ученые и инженеры задумывались давно. Американский логик Чарльз Сандерс Пирс первым осознал, что бинарная логика имеет сходства с работой электрических переключательных (контактных) схем. Компьютер работает на электричестве, любая информация представлена в компьютере в виде электрических импульсов. Рассмотрим реализацию логических элементов через электрические контактные схемы. Контакты обозначены латинскими буквами.
Последовательное соединение контактов. Цепь с последовательным соединением соответствует логической операции И (конъюнкции).
Параллельное соединение контактов Цепь с параллельным соединением соответствует логической операции ИЛИ (дизъюнкции).
Логическая операция НЕ (инверсия) реализуется через контактную схему электромагнитного реле.

&
Логические схемы – схемы, выполняющие операции преобразования: запоминания, пересылки двоичных битов информации в компьютере
Логический элемент (вентиль) – часть электронной логической схемы, которая выполняет элементарную логическую операцию. К элементарным логическим операциям реализуемым на логических микросхемах относятся операции: и, или, не, и-или, и-не, или-не, и-или-не и др.
Логический элемент И - конъюнктор.&
Х
Y Х&Y
Логический элемент ИЛИ – дизъюнктор.
X
Y X∨Y
Логический элемент НЕ – инвертор.
Х _
Х

Задания:
Упростить логическое выражение.
Построить таблицу истинности.
Построить логическую схему.
Показать. Что схема работает в соответствии с таблицей истинности.
___ ____
Выражение: F = A&B + B&C
___ ___ _ _ _ _ _ _ _
Ответ: F = A&B + B&C = A + B + B + C = A + B + C.
А
В
С

Задание для самостоятельной работы:
_________ _ ________ __ _____ __
1) F = X&Y + Y&Z + Z&X =Y&(X + Z) +Z&X = Y + X + Y + Z&X =
_ _ _ _ _ _ _ _ _
Y + X&Z + Z&X = Y + X&(Z + Z) = Y + X
2) F = A&B + D + ¬(A + ¬B) = A&B + D + ¬ A&B = B&(A + ¬ A) + D = B + D.

Упростить электрическую схему и построить электрическую и логическую схемы результата.

Решение

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

Сумматор –
это электронная логическая схема, выполняющая суммирование двоичных чисел.
В целях максимального упрощения работы компьютера все многообразие математических операций в процессоре сводится к сложению двоичных чисел. Поэтому главной частью процессора является сумматор, который обеспечивает такое сложение. При сложении двоичных чисел образуется сумма в данном разряде, при этом возможен перенос в старший разряд. Обозначим слагаемые А и В, сумму S и перенос Р. Построим таблицу сложения одноразрядных двоичных чисел с учетом переноса в старший разряд.
Cоставим булево выражение по этой таблице:
_ _
S = A&B + A&B; P = A&B
Упростим формулу для S:
_ _ _ _
A&B = A&A +A&B = A&(A + B),
_ _ _ _
A&B = A&B +B&B = B&(A + B).
_ _ _ _
S = A&B + A&B = A&(A + B) + B&(A + B) =
_ _ ____
(A + B) &(A + B) = (A + B)&A&B.

Схема сумматора
A
B 1 & S
&
P
1
&
&

Триггер. Регистры.
Триггер – устройство памяти компьютера для хранения одного бита информации.
Это устройство позволяет запоминать, хранить и считывать информацию. Триггер может находиться в одном из двух устойчивых состояний, которые соответствуют логической»1» и логическому «0». Триггер способен почти мгновенно переходить из одного электрического состояния в другое и наоборот. Самый распространенный триггер – SR-триггер ( S и R от английских слов set – установка, reset – сброс). Он имеет два входа S и R, два выхода Q и ¬Q. На каждый из входов подаются входные сигналы в виде кратковременных импульсов «1», отсутствие импульса – «0».
Для построения триггера достаточно двух логических элементов «ИЛИ» и двух элементов «НЕ».

Запрещено
При подаче сигнала на вход S триггер переходит в устойчивое единичное состояние.
При подаче сигнала на вход R триггер сбрасывается в устойчивое нулевое состояние.
При отсутствии входных сигналов триггер сохраняет тот сигнал, который был установлен входным импульсом.
Если на два входа подан сигнал, то появляется неоднозначный результат, поэтому такая комбинация запрещена.