Логика (др.греч. λογικος) – это наука о том, как правильно рассуждать, делать выводы, доказывать утверждения.
История логики насчитывает около двух с половиной тысячелетий. Первые учения о формах и способах мышления возникли в Древнем Китае и Индии. Основоположником формальной логики является Аристотель (384-322 гг. до н.э.) – древнегреческий философ, который впервые отделил логические формы мышления от его содержания.
Логические основы
построения
компьютера
Логика (др.греч. λογικος) – это наука о
том, как правильно рассуждать, делать
выводы, доказывать утверждения.
Second
Page
История логики насчитывает около двух
с половиной тысячелетий. Первые
учения о формах и способах мышления
возникли в Древнем Китае и Индии.
Основоположником формальной логики
является Аристотель (384322 гг. до
н.э.) – древнегреческий философ,
который впервые отделил логические
формы мышления от его содержания.
• Your Text here
• Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed
diam nonummy nibh euismod tincidunt ut laoreet dolore
magna aliquam erat volutpat. Ut wisi enim ad minim veniam,
quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut
aliquip ex ea commodo consequat.
• Duis autem vel eum iriure dolor in hendrerit in vulputate velit
esse molestie consequat, vel illum dolore eu feugiat nulla
Формальная логика отвлекается от
facilisis at vero eros et accumsan et iusto odio dignissim qui
конкретного содержания, изучает только
blandit praesent luptatum zzril delenit augue duis dolore te
feugait nulla facilisi.
истинность и ложность высказываний.
высказывание
Логическое
это
повествовательное предложение, относительно
которого можно однозначно сказать, истинно
оно или ложно.
–
Высказывание или нет?
• Your Text here
Красиво!
Сейчас идет дождь.
Жирафы летят на север.
У квадрата – 10 сторон и все разные.
Second
Page
ДА
ДА
ДА
• Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed
НЕТ
diam nonummy nibh euismod tincidunt ut laoreet dolore
magna aliquam erat volutpat. Ut wisi enim ad minim veniam,
НЕТ
quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut
НЕТ
aliquip ex ea commodo consequat.
НЕТ
• Duis autem vel eum iriure dolor in hendrerit in vulputate velit
esse molestie consequat, vel illum dolore eu feugiat nulla
facilisis at vero eros et accumsan et iusto odio dignissim qui
blandit praesent luptatum zzril delenit augue duis dolore te
feugait nulla facilisi.
В городе N живут 2 миллиона человек.
Который час?
История – интересный предмет.
Солнце есть спутник Земли.
2+3>4
Сегодня отличная погода.
СанктПетербург расположен на Неве.
Second
Музыка Баха слишком сложна.
Первая космическая скорость равна 7.8
Page
• Your Text here
км/сек.
Железо — металл.
Если один угол в треугольнике прямой, то
• Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed
diam nonummy nibh euismod tincidunt ut laoreet dolore
magna aliquam erat volutpat. Ut wisi enim ad minim veniam,
quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut
aliquip ex ea commodo consequat.
треугольник будет тупоугольным.
Если сумма квадратов двух сторон
треугольника равна квадрату третьей, то
• Duis autem vel eum iriure dolor in hendrerit in vulputate velit
он прямоугольный.
esse molestie consequat, vel illum dolore eu feugiat nulla
facilisis at vero eros et accumsan et iusto odio dignissim qui
blandit praesent luptatum zzril delenit augue duis dolore te
feugait nulla facilisi.
Алгебра логики – это математический
аппарат, который позволяет выполнять
действия над высказываниями.
Second
Page
• Your Text here
• Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed
diam nonummy nibh euismod tincidunt ut laoreet dolore
magna aliquam erat volutpat. Ut wisi enim ad minim veniam,
quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut
aliquip ex ea commodo consequat.
Алгебру логики называют
булевой алгеброй, по
имени английского
математика Джорджа Буля
(18151864),
разработавшего в XIXв. её
основные положения.
• Duis autem vel eum iriure dolor in hendrerit in vulputate velit
esse molestie consequat, vel illum dolore eu feugiat nulla
facilisis at vero eros et accumsan et iusto odio dignissim qui
blandit praesent luptatum zzril delenit augue duis dolore te
feugait nulla facilisi.
Обозначение высказываний
Высказывания обозначают латинскими буквами: A, B, X, Y.
A = Париж – столица Англии.
B = Число 11 является простым.
Second
Page
Любое высказывание может быть
ложно (0) или истинно (1).
• Your Text here
• Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed
diam nonummy nibh euismod tincidunt ut laoreet dolore
magna aliquam erat volutpat. Ut wisi enim ad minim veniam,
Составные высказывания строятся из
quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut
aliquip ex ea commodo consequat.
простых с помощью логических связок
(операций) «и», «или», «не», «если …
то», «тогда и только тогда» и др.
• Duis autem vel eum iriure dolor in hendrerit in vulputate velit
esse molestie consequat, vel illum dolore eu feugiat nulla
facilisis at vero eros et accumsan et iusto odio dignissim qui
blandit praesent luptatum zzril delenit augue duis dolore te
feugait nulla facilisi.
• На улице хорошая погода, и дети пошли гулять.
• Петя расскажет стихотворение, или Серёжа
пойдет к доске.
Логические выражения и логические
операции
Действия, которые производятся над высказываниями,
записываются в виде логических выражений.
Простое логическое выражение состоит из одного
Second
высказывания и не содержит логических операций, в
противном случае оно является сложным.
Page
Основные логические операции
• Your Text here
Название
Математическое
обозначение
• Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed
&,Ÿ,/\
diam nonummy nibh euismod tincidunt ut laoreet dolore
magna aliquam erat volutpat. Ut wisi enim ad minim veniam,
quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut
+,\/
aliquip ex ea commodo consequat.
Логическое умножение,
Логическое сложение,
Обозначение
дизъюнкция
конъюнкция
инверсия
Логическое отрицание,
• Duis autem vel eum iriure dolor in hendrerit in vulputate velit
esse molestie consequat, vel illum dolore eu feugiat nulla
facilisis at vero eros et accumsan et iusto odio dignissim qui
blandit praesent luptatum zzril delenit augue duis dolore te
feugait nulla facilisi.
Импликация, следование
если, то
тогда и только
не
и
или
Эквивалентность,
равносильность
тогда
Таблицы истинности
Все операции алгебры логики определяются
таблицами истинности значений.
Таблица истинности определяет значение
сложного высказывания при всех
возможных значениях, входящих в него
простых высказываний.
Количество строк в таблице истинности будет
зависеть от количества высказываний в
логическом выражении (если число
высказываний в логическом выражении N, то в
таблице будет 2N строк).
Инверсия логическое отрицание
Логическое отрицание делает истинное высказывание
ложным и, наоборот, ложное – истинным.
От лат. inversio
переворачиваю
А
0
1
не А
A A
1
0
А= Земля вращается вокруг Солнца. (истина)
¬А = Земля не вращается вокруг Солнца. (ложь)
Конъюнкция логическое умножение
От лат. conjunctio связываю
Результат логического умножения является
истинным тогда и только тогда, когда истинны
все входящие в него простые высказывания.
A
0
1
0
1
B
0
0
1
1
А и B
A∙B, A B
0
0
0
1
С= А & В
Учитель должен быть умным и справедливым.
А= Учитель должен быть умным.
В= Учитель должен быть справедливым.
От лат. disjunctio – различаю
Дизъюнкция логическое сложение
Результат логического сложения является истинным
тогда, когда истинно хотя бы одно из входящих в него
простых высказываний.
A
0
1
0
1
B
0
0
1
1
А или B
A+B, A B
0
1
1
1
С= А + В
В библиотеке можно взять книгу или встретить
знакомого.
А= В библиотеке можно взять книгу.
В= В библиотеке можно встретить знакомого.
От лат. implicatio – тесно связывать
Импликация логическое следование
Результат логического следования является
ложным тогда и только тогда, когда из истины
следует ложь.
A
0
1
0
1
B
0
0
1
1
Если А, то B
А B
1
0
1
1
Если идёт дождь, то на улице сыро.
А= Идет дождь.
В= На улице сыро.
От лат. aeguivalens – равноценное
А B
А тогда и только
тогда, когда В
Эквивалентность логическое равенство
Результат логического равенства является
истинным тогда и только тогда, когда оба
высказывания одновременно либо истинны, либо
ложны.
A
0
0
1
1
B
0
1
0
1
1
0
0
1
День сменяет ночь тогда и только тогда,
когда солнце скрывается за горизонтом.
Составление таблиц
истинности по логической
формуле
Постройте таблицу истинности для логического
выражения
A
0
1
0
1
B
0
0
1
1
A∙¬B
¬B
1
1
0
0
A∙¬B
0
1
0
0
Составление таблиц истинности по
логической формуле
Постройте таблицу истинности для логического выражения
(A+¬B)·C
A
0
1
0
1
0
1
0
1
B
0
0
1
1
0
0
1
1
C
0
0
0
0
1
1
1
1
¬B
A+¬B
(A+¬B)·C
1
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
0
0
0
0
1
1
0
1
ОПРЕДЕЛЕНИЕ
ЛОГИЧЕСКОГО
ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ
ИСТИННОСТИ
Условимся называть задачу построения таблицы
истинности по формуле сложного высказывания –
прямой задачей. Тогда обратная задача –
построение логической формулы по таблице
истинности. Полученную формулу будем записывать
в виде логической функции.
Приведена таблица истинности для аргументов А, B,
по которой надо составить логическое выражение
F(A,B).
A
0
0
1
1
B
0
1
0
1
F(A,B)
1
0
1
0
Алгоритм нахождения искомой формулы:
A
0
0
1
1
B
0
1
0
1
F(A,B)
1
0
1
0
Отмечаем
Записываем
¬A∙¬B
A∙¬B
1. Выделить в таблице истинности строки, в которых
выражение истинно (1);
2. Соединить операцией И (умножение)
содержимое столбцов аргумента для выбранных строк.
При этом если в таблице «0», пишем входной сигнал с
отрицанием, а если в таблице «1», то без отрицания.
3. Соединить операцией ИЛИ (сложение)
полученные выражения.
F(A,B)= ¬A∙¬B + A∙¬B
4. Упростить искомую формулу (по возможности).
Пример 2.
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F(A,B,C) Отмечаем Записываем
1
0
0
0
0
0
0
1
¬A∙¬B∙¬C
A∙B∙C
F(A, B, C) = ¬A∙¬B∙¬C + A∙B∙C
Пример 3.
A
0
0
1
1
B
0
1
0
1
F(A,B,C) Отмечаем Записываем
0
1
1
1
¬ A ∙ B
A∙ ¬ B
A ∙ B
F(A, B) = ¬A∙B + A∙ ¬ B + A∙B
Пример 4.
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F(A,B,C) Отмечаем
1
0
1
0
1
0
1
0
F(A, B, C) = ¬C
Пример 5.
A
0
0
1
1
B
0
1
0
1
F(A,B,C) Отмечаем
0
0
1
1
F(A, B) = A
A
0
0
1
1
B
0
1
0
1
F(A,B)
1
0
1
0
A
0
0
1
1
B
0
1
0
1
F(A,B)
1
1
0
0
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F(A,B,C)
1
0
1
0
1
1
1
1
3)3
4)4
2) 2
2)6
4)4
4)4
3)3
3)3
2) 2
Задания из ГИА
1. Для какого из указанных значений числа Х истинно выражение
(X<3) & ((X<2) V (X>2))?
1) 1
2. Для какого из указанных значений числа Х истинно выражение
(X<4) & (X>2) & (X<>2)?
1) 1
3. Для какого из указанных значений числа Х истинно выражение
(X>4) & (X<7) & (X<6)?
1) 5
4. Для какого из указанных значений числа Х истинно выражение
(X>1) & (X>2) & (X≠3)?
1) 1
5. Для какого из указанных значений числа X ложно выражение
(X > 2) ИЛИ НЕ (X > 1)?
1) 1
6. Для какого из указанных значений числа X истинно выражение
(X < 3) & ¬(X < 2)?
1) 1
2) 2
7. Для какого из указанных значений числа X истинно выражение
(X > 2) & ( (X < 4) \/ (X > 4))?
1) 1
2) 2
3)3
3)3
4)4
4)4
3)3
3)3
4)4
4)4
2) 2
2) 2
Логические элементы и
логические схемы компьютера.
Как при строительстве дома
применяют различного рода типовые
блоки: кирпичи, рамы, двери и т. п.,
так и при разработке компьютера
используют типовые электронные
схемы. Каждая схема состоит из
определенного набора типовых
электронных элементов.
Электронным элементом называется
соединение различных деталей – в
первую очередь, диодов и
транзисторов, а также резисторов,
конденсаторов, в виде
электрической схемы, выполняющей
некоторую простейшую функцию.
Электронный элемент, реализующий
логическую функцию, называется
логическим вентилем.
Логические основы компьютеров
Логические элементы компьютера
Инвертор
A
A
A
B
Конъюнкто
р
&
BA
И
Дизъюнктор
1
BA
НЕ
A
B
ИЛИ
К. Поляков, 20072010
http://kpolyakov.narod.ru
Тысячи микроскопических электронных
переключателей в кристалле
интегральной схемы сгруппированы в
системы, выполняющие логические
операции, т. е. операции с
предсказуемыми результатами и
арифметические операции над
двоичными числами. Соединенные в
различные комбинации, логические
вентили дают возможность компьютеру
решать задачи, используя язык
двоичных кодов.
Электронным элементом называется
соединение различных деталей – в
первую очередь, диодов и
транзисторов, а также резисторов,
конденсаторов, в виде
электрической схемы, выполняющей
некоторую простейшую функцию.
Электронный элемент, реализующий
логическую функцию, называется
логическим вентилем.
Построение логических схем
1.Определить число логических переменных.
2.Определить количество базовых логических
операций и их порядок.
3.Изобразить для каждой логической операции
соответствующий ей вентиль.
4.Соединить вентили в порядке выполнения
логических операций.
Пример 1
Пусть X = истина, Y = ложь. Составить
логическую схему для следующего логического
выражения:
F = X+Y*X
1. Две переменные: X и У.
2. Две логические операции: X+Y*X.
3. Строим схему:
2 1
X
Y
1
0
&
1
F
&
1
Ответ: 1+0*1=1.
Пример 2
Постройте логическую схему, соответствующую
логическому выражению F = X*Y+¬(Y+X).
Вычислить значения выражения для X=1, Y=0.
1
0
1
0
&
1
1
Постройте логические схемы:
1. F = A*(B+C)
2. F = ¬ B*(¬A*B+A)
3. F = D+A*B*C*(¬B+¬C)
4. F = (C*¬A)+¬(A*B+B*C)
если A=1, B=1, C=1
5. F = A+B*¬C,
6. F = ¬(A+B*C), если A=0, B=1, C=1
7. F= ¬A+B*C, если A=1, B=0, C=1
8. F = (A+B)*(C+B),
1
9. F = ¬(A*B*C),
1
10.F = ¬(A*B*C)+(B*C+ ¬A), если A=1, B=1, C=0
11.F = B* ¬A+ ¬B*A, ЕСЛИ A=0, B=0
если A=0, B=0, C=1
если A=0, B=1, C=0
1
1
0
1
0
Постройте логическое выражение к логическим схемам:
&
1
A
B
&
1
A
B
C
D
&
&
&
Триггер – логическая схема, способная сохранять одно
из 2 состояний до подачи нового сигнала на вход. Это,
по сути, разряд памяти, способный хранить 1 бит
информации.
Регистр – устройство , состоящее из
последовательности триггеров. Регистр предназначен
для хранения многоразрядного двоичного числового
кода, которым можно представлять и адрес, и команду,
и данные.
ponyatie_ob_algebre_logiki1___logicheskie_operacii.ppt
