Логические основы компьютера логические операции. Основы логики и логические основы компьютера

Алгебра логики и логические основы компьютера

Что такое алгебра логики?

Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

Что же собой представляет алгебра логики? Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два значения: 0, либо 1.

Что такое простое логическое высказывание ? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.

Логические операции. Дизъюнкция, конъюнкция и отрицание(инверсия)

Так как же связываются между собой простые логические высказывания, образуя сложные? В естественном языке мы используем различные союзы и другие части речи. Например, «и», «или», «либо», «не», «если», «то», «тогда». Пример сложных высказываний: «у него есть знания и навыки», «она приедет во вторник, либо в среду», «я буду играть тогда , когда сделаю уроки», «5 не равно 6». Как мы решаем, что нам сказали правду или нет? Как-то логически, даже где-то неосознанно, исходя из предыдущего жизненного опыта, мы понимает, что правда при союзе «и» наступает в случае правдивости обоих простых высказываний. Стоит одному стать ложью и все сложное высказывание будет лживо. А вот, при связке «либо» должно быть правдой только одно простое высказывание, и тогда все выражение станет истинным.

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

Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают & , дизъюнкцию - || , а отрицание - чертой над переменной, обозначающей высказывание.

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

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

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

Таблицы истинности

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

Логические основы компьютера

В ЭВМ используются различные устройства, работу которых прекрасно описывает алгебра логики. К таким устройствам относятся группы переключателей, триггеры, сумматоры.

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

ФОРМЫ МЫШЛЕНИЯ

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

Основные формы мышления

Основными формами мышления являются: ПОНЯТИЯ,
СУЖДЕНИЯ, УМОЗАКЛЮЧЕНИЯ.
ПОНЯТИЕ - форма мышления, в которой отражаются
существенные признаки отдельного объекта или класса
однородных объектов.
Примеры: портфель, трапеция, ураганный ветер.
Понятие имеет две стороны: содержание и объем.

Основные формы мышления

СУЖДЕНИЕ – это форма мышления, в которой что-либо
утверждается или отрицается об объектах, их свойствах
и отношениях.
Суждениями обычно являются
повествовательными предложениями, которые могут
быть или истинными или ложными.
«Берн - столица Франции»,
«Река Кубань впадает в Азовское море»,
«2>9», «3×5=10»

Основные формы мышления

УМОЗАКЛЮЧЕНИЕ – это форма мышления,
посредством которой из одного или нескольких истинных
суждений, называемых посылками, мы по
определенным правилам вывода получаем новое
суждение (заключение).
Все металлы - простые вещества. Литий металл.→ Литий - простое вещество.
Один из углов треугольника равен 90º. → Этот
треугольник прямоугольный.

АЛГЕБРА ВЫСКАЗЫВАНИЙ

В основе работы логических схем и устройств персонального
компьютера лежит специальный математический аппарат математическая логика. Математическая логика изучает
вопросы применения математических методов для решения
логических задач и построения логических схем. Знание логики
необходимо при разработке алгоритмов и программ, так как в
большинстве языков программирования есть логические
операции.
Английский математик Джордж Буль (1815 - 1864 г.) создал
логическую алгебру, в которой высказывания обозначены
буквами. Сочинение Джорджа Буля, в котором подробно
исследовалась эта алгебра, было опубликовано в 1854 г. Оно
называлось «Исследование законов мысли» («Investigation of
the Laws of Thought»). Отсюда ясно, что Буль рассматривал
свою алгебру как инструмент изучения законов человеческого
мышления, то есть законов логики.
Алгебру логики иначе называют алгеброй высказываний. В
математической логике суждения называются высказываниями.

ВЫСКАЗЫВАНИЕ - это повествовательное предложение, о котором
можно сказать, что оно или истинно или ложно.
Земля - планета Солнечной системы. (Истинно)
2 · 2 =5 (Ложно)
Не всякое предложение является высказыванием:
1) Восклицательные и вопросительные предложения высказываниями не
являются.
“Какого цвета этот дом?”; “Пейте томатный сок!”
2) Не являются высказываниями и определения.
Определения не бывают истинными или ложными, они лишь
фиксируют принятое использование терминов.
“Назовем медианой отрезок, соединяющий вершину треугольника с
серединой противоположной стороны”.
3) Не являются высказываниями и предложения типа “Он сероглаз”
или
“х- 4х + 3=0” - в них не указано о каком человеке идет речь или для
какого числа х верно равенство. Такие предложения называются
высказывательными формами.
Высказывательная форма - это повествовательное предложение,
которое прямо или косвенно содержит хотя бы одну переменную и
становится высказыванием, когда все переменные замещаются своими
значениями.

Высказывания могут быть простыми и сложными.
Высказывание считается простым, если никакую
его часть нельзя рассматривать как отдельное
высказывание.
Высказывание, которое можно разложить на
части, будем называть сложным, а неразложимое далее
высказывание - простым.
Сложное высказывание получается путем объединения
простых высказываний логическими связками - НЕ, И,
ИЛИ. Значение истинности сложных высказываний зависит от
истинности входящих в них простых высказываний и
объединяющих их связок.
Например, даны простые высказывания:
На улице идет дождь.
На улице светит солнце.
На улице пасмурная погода.
Составим из них сложные высказывания:
На улице идет дождь и на улице светит солнце.
На улице светит солнце или на улице пасмурная погода.
Неверно что на улице идет дождь.

В математической логике не рассматривается
конкретное содержание высказывания, важно только,
истинно оно или ложно. Поэтому высказывание
можно представить некоторой переменной
величиной, значением которой может быть
только 0 или 1. Если высказывание истинно, то
его значение равно 1, если ложно - 0.
Простые высказывания назвали логическими
переменными и для простоты записи их обозначают
латинскими буквами: А, В, С…
Луна является спутником Земли. А = 1
Москва – столица Германии. В = 0
Сложные высказывания называются логическими
функциями. Значения логической функции также
может принимать значения только 0 или 1.

10. БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

В алгебре высказываний, как и в обычной алгебре,
вводится ряд операций. Логические связки И,
ИЛИ и НЕ заменяются логическими операциями:
конъюнкцией, дизъюнкцией и инверсией. Это
основные логические операции, при помощи
которых можно записать любую логическую
функцию.

11. 1. Логическая операция ИНВЕРСИЯ (ОТРИЦАНИЕ)

соответствует частице НЕ
обозначается черточкой над именем
переменной или знаком ¬ перед переменной
Инверсия логической переменной истинна,
если сама переменная ложна, и, наоборот,
инверсия ложна, если переменная истинна.
Таблица истинности инверсии имеет вид:
A
0
A
1
0
1

12. 2. Логическая операция ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ)

соответствует союзу ИЛИ
обозначается знаком v или + или ║
Дизъюнкция двух логических переменных ложна тогда и только
тогда, когда оба высказывания ложны.
Это определение можно обобщить для любого количества
логических переменных, объединенных дизъюнкцией.
А v В v С =0, только если А=0, В=0, С=0.
Таблица истинности дизъюнкции имеет следующий вид:
A
0
B
0
A B
0
1
1
1
0
1
1
1
1
0

13. 3. Логическая операция КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ)

соответствует союзу И
обозначается знаком & или Λ, или ·
Конъюнкция двух логических переменных истинна тогда
и только тогда, когда оба высказывания истинны.
Это определение можно обобщить для любого
количества логических переменных, объединенных
конъюнкцией.
А & В & С=1, только если А=1, В=1, С=1.
Таблица истинности конъюнкции имеет следующий вид:
A
B
A B
0
0
0
0
1
0
1
0
0
1
1
1

14. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ

Сложные высказывания можно записывать в виде формул. Для этого
простые логические высказывания нужно обозначить как логические
переменные буквами и связать их с помощью знаков логических операций.
Такие формулы называются логическими выражениями. Например:
(A B & C)
(A B) & (A B)
Чтобы определить значение логического выражения необходимо
подставить значения логических переменных в выражение и выполнить
логические операции. Операции в логическом выражении выполняются
слева направо с учетом скобок в следующем порядке:
1. инверсия;
2. конъюнкция;
3. дизъюнкция;
Для изменения указанного порядка выполнения логических операций
используются круглые скобки.

15. Таблицы истинности

Для каждого составного высказывания (логического выражения) можно
построить таблицу истинности, которая определяет истинность или
ложность логического выражения при всех возможных комбинациях
исходных значений простых высказываний (логических переменных).
При построении таблиц истинности целесообразно руководствоваться
определенной последовательностью действий:
1) записать выражение и определить порядок выполнения операций
2) определить количество строк в таблице истинности. Оно равно
количеству возможных комбинаций значений логических переменных,
входящих в логическое выражение (определяется по формуле Q=2n ,
где n - количество входных переменных)
3) определить количество столбцов в таблице истинности (= количество
логических переменных + количество логических операций)
4) построить таблицу истинности, обозначить столбцы (имена переменных
и обозначения логических операций в порядке их выполнения) и
внести в таблицу возможные наборы значений исходных логических
переменных.
5) заполнить таблицу истинности, выполняя базовые логические операции
в необходимой последовательности и в соответствии с их таблицами
истинности

16.

Теперь мы можем определить значение логической функции для
любого набора значений логических переменных.
Например, построим таблицу истинности для логической функции:
F (A, B ,C) A (C В)
Количество входных переменных в заданном выражении равно
трем (A,B,C). Значит, количество входных наборов, а значит и строк
Q=23=8. Количество столбцов равно 6 (3 переменные + 3 операции).
Столбцы таблицы истинности соответствуют значениям исходных
выражений A,B,C, промежуточных результатов Aи,(аCтакже
В)
искомого окончательного значения сложного арифметического
выражения
A (C В)

17.

A (C В)
A
B
C
A
BVC
A (C В)

18.

A (C В)
A
B
C
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
A
B V C A (C В)

19.

A
B
C
A
BVC
A (C В)
0
0
0
1
0
0
0
0
1
1
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
1
0
1
0
Задание. Постройте таблицу истинности для логического выражения:
(A B) (A В)

20.

(A B) & (A B)
(A B) & (A B)
А
В
A B
A
0
0
1
0
1
0
0
1
1
1
1
0
1
1
0
0
1
0
1
1
1
0
1
1
A B

21. РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ

22.

ЗАДАЧА 1.
Разбирается дело Лёнчика, Пончика и Батончика. Кто-то из них нашел и утаил клад. На
следствии каждый из них сделал по два заявления.
Батончик: «Я не делал этого. Пончик сделал это»
Лёнчик: «Пончик не виновен. Батончик сделал это»
Пончик: «Я не делал этого. Лёнчик не делал этого»
Суд установил, что один из них дважды солгал, другой - дважды сказал правду, третий -
один раз солгал, один раз сказал правду. Кто утаил клад?
Решение:
Введём обозначения: Б –клад утаил Батончик, П - клад утаил Пончик, Л - клад
утаил Лёнчик. Рассмотрим три возможных варианта – виноват Батончик, виноват Пончик,
виноват Лёнчик. При таких вариантах получаем следующие значения высказываний трёх
обвиняемых.
Возможные варианты
Высказывания
Батончика
Высказывания
Лёнчика
Высказывания
Пончика
Б
Л
П
¬Б
П
¬П
Б
¬П
¬Л
Соответств
ие условию
задачи
1
0
0
0
0
1
1
1
1
-
0
0
1
1
1
0
0
0
1
+
0
1
0
1
0
1
0
1
0
-
В первом варианте один солгал дважды, а двое сказали правду дважды, что не соответствует
условию задачи. В третьем варианте все один раз сказали правду и один раз солгали, что
также не соответствует условию задачи. Во втором варианте один дважды солгал, другой
дважды сказал правду, а третий один раз сказал правду, а один раз солгал, что соответствует
условию задачи. Следовательно клад утаил Пончик.

23.

Задача 2.
В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита.
Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях.
Один считает, что первой будет Наташа, а Маша будет второй.
Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.
Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?
Решение:
Введём обозначения: Н1 – Наташа на 1 месте, М2 – Маша на 2 месте, Л2 – Люда на 2 месте, Р4 – Рита на 4
месте, Р3 – Рита на 3 месте, Н2 – Наташа на 2 месте. Занесём возможные варианты высказываний трёх
болельщиков в таблицу с учётом того, что каждый из болельщиков оказался прав только в одном из своих
прогнозов:
Высказывания 1-ого
болельщика
Высказывания 2-ого
болельщика
Высказывания 2-ого
болельщика
Соответствие
условию
задачи
Н1
М2
Л2
Р4
Р3
Н2
0
1
0
1
0
1
-
0
1
0
1
1
0
-
0
1
1
0
1
0
-
0
1
1
0
0
1
-
1
0
0
1
0
1
-
1
0
0
1
1
0
-
1
0
1
0
0
1
-
1
0
1
0
1
0
+
Из анализа таблицы видно, что условию задачи соответствует только последняя строка, значит первое место
заняла Наташа, второе – Люда, третье – Рита, а Маша –четвёртое.

24.

Задача 3.
Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и
арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает
китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии
выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык
изучает каждый из молодых людей?
Решение:
Введём обозначения: ВК – Вадим изучает китайский язык, СК – Сергей изучает китайский язык,
МА - Михаил изучает арабский язык. Занесём в таблицу возможные варианты значений
высказываний с учётом условия задачи, что одно из утверждений верно, а два - ложны:
ВК
¬ СК
¬ МА
ВК
СК
МА
Соответствие
условию
задачи
1
0
0
1
1
1
-
0
0
1
0
1
0
+
0
1
0
0
0
1
-
Возможные варианты высказываний
Проанализируем строки в трёх последних столбцах. Условию задачи соответствует
только вторая строка, значит Сергей изучает китайский язык, Михаил – японский (так как
он не изучает арабский), тогда Вадим изучает арабский язык.

25.

Задача 4. Три одноклассника - Влад, Тимур и Юра, встретились спустя 10 лет после окончания
школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил
туризм, другой бег, страсть третьего - регби.
Юра сказал, что на туризм ему не хватает времени, хотя его сестра - единственный врач в семье,
заядлый турист. Врач сказал, что он разделяет увлечение коллеги.
Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква
их имен.
Определите, кто чем любит заниматься в свободное время и у кого какая профессия.
Решение: Здесь исходные данные разбиваются на тройки (имя - профессия - увлечение).
Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он
турист.
Имя
Юра
Профессия
врач
Увлечение
туризм
Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно
врач - Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно
второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его
имени - Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р".
Следовательно, окончательно имеем:
Имя
Юра
Тимур
Влад
Профессия
физик
врач
юрист
Увлечение
бег
туризм
регби
Ответ. Влад - юрист и регбист, Тимур - врач и турист, Юра - физик и бегун.

26. Задачи для самостоятельного решения

Задача 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.
- Вот увидишь, Шумахер не придет первым, - сказал Джон. Первым будет Хилл.
- Да нет же, победителем будет, как всегда, Шумахер, - воскликнул Ник. - А об Алези и говорить нечего, ему не
быть первым.
Питер, к которому обратился Ник, возмутился:
- Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба
предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?
Задача 2. В спортивных соревнованиях принимали участие пять команд: "Вымпел", "Метеор", "Нептун", "Старт" и
"Чайка". Об их итогах соревнования имеется пять высказываний:
1) Второе место занял "Вымпел", a "Cтарт" оказался на третьем.
2) Хорошо выступала команда "Нептун", она стала победителем, а "Чайка" вышла на второе место.
3) Да нет же, "Чайка" заняла только третье место, а "Нептун"- был последним.
4) Первое место по праву завоевал "Cтарт", а "Метеор" был 4-м.
5) Да, "Метеор", действительно, был четвертым, а "Вымпел" был 2-м.
Известно, что команды не делили места между собой и что в каждом высказывании одно утверждение
правильное, а другое нет.
Как распределились места между командами?
Задача 3 Три дочери писательницы Дорис Кей - Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели
известность в разных видах искусств - пении, балете и кино. Все они живут в разных городах, поэтому Дорис
часто звонит им в Париж, Рим и Чикаго.
Известно, что:
Джуди живет не в Париже, а Линда - не в Риме;
парижанка не снимается в кино;
та, кто живет в Риме, певица;
Линда равнодушна к балету.
Где живет Айрис, и какова ее профессия?

27.

Логические операции «И», «ИЛИ», «НЕ» лежат
в основе работы преобразователей
информации любого компьютера
американский математик,
доказал применимость
булевой алгебры в теории
контактных и релейноконтактных схем (в 1938
году)
Клод Шеннон
(1916 г.)
27

28. Логический элемент компьютера

- это часть электронной логичеcкой схемы, которая реализует элементарную
логическую функцию.
Логическими элементами компьютеров являются электронные схемы И,
ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и другие (называемые также вентилями), а
также триггер.
С помощью этих схем можно реализовать любую логическую функцию,
описывающую работу устройств компьютера. Обычно у вентилей бывает от
двух до восьми входов и один или два выхода.
Чтобы представить два логических состояния - “1” и “0” в вентилях,
соответствующие им входные и выходные сигналы имеют один из двух
установленных уровней напряжения. Например, +5 вольт и 0 вольт.
Высокий уровень обычно соответствует значению “истина” (“1”), а низкий -
значению “ложь” (“0”).
Каждый логический элемент имеет свое условное обозначение, которое
выражает его логическую функцию, но не указывает на то, какая именно
электронная схема в нем реализована. Это упрощает запись и понимание
сложных логических схем.
Работу логических элементов описывают с помощью таблиц истинности.
Таблица истинности это табличное представление логической схемы
(операции), в котором перечислены все возможные сочетания значений
истинности входных сигналов (операндов) вместе со значением истинности
выходного сигнала (результата операции) для каждого из этих сочетаний.

29.

1
0
&
Логический элемент «И»,
преобразует входные
0
сигналы и выдает
результат логического
умножения
29

30.

1
0
V
Логический элемент
1
«ИЛИ», преобразует
входные сигналы и
выдает результат
логического сложения.
30

31.

1
1
0
Логический элемент
«НЕ». Преобразует
входной сигнал и
выдает результат
логического отрицания.
31

32.

А
В
&
F1
1
F2
V
F3
A&BvB
Функциональная схема логического устройства
Структурная формула ЛУ
Зная функциональную схему, можно составить
структурную формулу данного ЛУ.
Анализируя структурную формулу, можно создать
функциональную схему и понять, как работает данное 32ЛУ.

33.

Какие логические операции лежат в основе
преобразователей информации в ПК?
Как называются логические элементы ПК?
Что такое структурная формула?
Что можно увидеть на функциональной схеме?
Какие устройства ПК построены на логических
элементах?
Какие основные операции выполняет центральный
процессор?
Как «работает» память ПК?
Не знаете?
тогда идем дальше!
33

34.

Так как все многообразие операций в ПК сводится
к сложению двоичных чисел,
то главной частью процессора (АЛУ) является сумматор.
Рассмотрим сложение одноразрядных двоичных чисел:
Слагаемые Перено Сумм
с
а
А
В
Р
S
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
34

35.

Слагаемые
А
В
0
0
Перенос
Р
0
Сумма
S
0
0
1
0
1
1
0
0
1
1
1
1
0
P=A&B
S=(А v B) & (A & B)
Докажем это, построив таблицу истинности для данного ЛВ
А
B
1
AVB
2
A&B
3
NOT(2)
4
1&3
0
0
0
1
0
1
0
0
1
1
0
1
1
0
1
0
1
1
1
1
1
1
0
0
35

36.

S=(А v B) & (A & B)
P=A&B
A
Теперь, на основе полученных логических выражений,
можно построить схему данного устройства
P
&
B
1
&
S
V
36

37.

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

38.

Для хранения информации в ОП и регистрах ЦП
применяется устройство ТРИГГЕР. Ячейка
памяти состоит из 8, 16 или 32 триггеров, что и
определяет разрядность ЦП. Триггер строится из
двух элементов «ИЛИ» и двух элементов «НЕ».
S(1)
V
1
0
1
0
V
1
1
R
В обычном состоянии на входы подан «0». Для записи на вход S подается
«1». Он его будет хранить и даже после того, как сигнал на входе «S»
исчезнет. Чтобы сбросить информацию, подается «1» на вход R (Reset),
после чего триггер возвращается к исходному «нулевому» состоянию.
38

39. Триггер

Триггер - это электронная схема, широко применяемая в
регистрах компьютера для надёжного запоминания одного
разряда двоичного кода. Триггер имеет два устойчивых
состояния, одно из которых соответствует двоичной единице,
а другое - двоичному нулю.
Термин триггер происходит от английского слова trigger -
защёлка, спусковой крючок. Для обозначения этой схемы в
английском языке чаще употребляется термин flip-flop, что в
переводе означает "хлопанье". Это звукоподражательное
название электронной схемы указывает на её способность
почти мгновенно переходить ("перебрасываться") из одного
электрического состояния в другое и наоборот.
Самый распространённый тип триггера - так называемый
RS-триггер (S и R, соответственно, от английских set -
установка, и reset - сброс).

40.

Несколько триггеров можно
объединить в группы - регистры
и использовать в качестве
запоминающих устройств (ЗУ).
Если в регистр входит N триггеров,
то при таком ЗУ можно запоминать
N-разрядные двоичные слова.
ОЗУ ЭВМ часто конструируется в
виде набора регистров.
Один регистр образует одну
ячейку памяти, каждая из которых
имеет свой номер
Таким образом, ЭВМ
состоит из огромного числа
Отдельных логических элементов,
образующих все ее узлы и память.
т
т
т

Общие понятия n ЛОГИКА - это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений. n Математическая логика одна из областей общей логики, развиваемая применительно к потребностям математики (и вычислительной техники). В ее составе: логика высказываний (исчисление высказываний; алгебра логики; булева алгебра). логика предикатов (исчисление предикатов). метаматематика (изучение аксиоматического построения наук, в частности той же математики).

ФОРМЫ МЫШЛЕНИЯ n ЛОГИКА - это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений. n Логика изучает мышление как средство познания объективного мира. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Формальная логика связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком. Математическая логика изучает только умозаключения со строго определенными объектами и суждениями, для которых можно однозначно решить, истинны они или ложны. Идеи и аппарат логики используется в кибернетике, вычислительной технике и электротехнике (построение компьютеров основано на законах математической логики). В основе логических схем и устройств ПК лежит специальный математический аппарат, использующий законы логики. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции. n n n

Основные формы мышления Основными формами мышления являются: ПОНЯТИЯ, СУЖДЕНИЯ, УМОЗАКЛЮЧЕНИЯ. ПОНЯТИЕ форма мышления, в которой отражаются существенные признаки отдельного объекта или класса однородных объектов. Примеры: портфель, трапеция, ураганный ветер. Понятие имеет две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов. Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер - это универсальное электронное устройство для автоматической обработки информации, предназначенное для одного пользователя» . Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров. СУЖДЕНИЕ – это форма мышления, в которой что либо утверждается или отрицается об объектах, их свойствах и отношениях. Суждениями обычно являются повествовательными предложениями, которые могут быть или истинными или ложными. «Берн - столица Франции» , «Река Кубань впадает в Азовское море» , « 2>9» , « 3× 5=10» УМОЗАКЛЮЧЕНИЕ – это форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем новое суждение (заключение). Все металлы - простые вещества. Литий - металл. → Литий - простое вещество. Один из углов треугольника равен 90º. → Этот треугольник прямоугольный.

АЛГЕБРА ВЫСКАЗЫВАНИЙ n В основе работы логических схем и устройств персонального компьютера лежит специальный математический аппарат математическая логика. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции. n Английский математик Джордж Буль (1815 - 1864 г.) создал логическую алгебру, в которой высказывания обозначены буквами. Сочинение Джорджа Буля, в котором подробно исследовалась эта алгебра, было опубликовано в 1854 г. Оно называлось «Исследование законов мысли» («Investigation of the Laws of Thought»). Отсюда ясно, что Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления, то есть законов логики. Алгебру логики иначе называют алгеброй высказываний. В математической логике суждения называются высказываниями.

ВЫСКАЗЫВАНИЕ - это повествовательное предложение, о котором можно сказать, что оно или истинно или ложно. Например: Земля - планета Солнечной системы. (Истинно) 2+8

Высказывания могут быть простыми и сложными. Высказывание считается простым, если никакую его часть нельзя рассматривать как отдельное высказывание Некоторые высказывания можно разложить на отдельные части, при этом каждая такая часть будет самостоятельным высказыванием. Например, высказывание “Сегодня в 4 часа дня я был в школе, а к 6 часам вечера пошел на каток” состоит из 2 частей. Высказывание может состоять и из большего количества частей. Высказывание, которое можно разложить на части, будем называть сложным, а неразложимое далее высказывание - простым. Сложное высказывание получается путем объединения простых высказываний логическими связками - НЕ, И, ИЛИ. Значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и объединяющих их связок. Например, даны простые высказывания: На улице идет дождь. На улице светит солнце. На улице пасмурная погода. Составим из них сложные высказывания: На улице идет дождь и на улице светит солнце. На улице светит солнце или на улице пасмурная погода. Неверно что на улице идет дождь.

n n n В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1. Если высказывание истинно, то его значение равно 1, если ложно - 0. Простые высказывания назвали логическими переменными и для простоты записи их обозначают латинскими буквами: А, В, С… Луна является спутником Земли. А = 1 Москва – столица Германии. В = 0 Сложные высказывания называются логическими функциями. Значения логической функции также может принимать значения только 0 или 1.

n Аргументы логических функций - двоичные величины. Логические функции могут быть заданы: аналитически (формулы с использованием специальных символов); таблично; графически (геометрически; используется эта форма редко обычно для количества аргументов не более 3). n

БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ В алгебре высказываний, как и в обычной алгебре, вводится ряд операций. Логические связки И, ИЛИ и НЕ заменяются логическими операциями: конъюнкцией, дизъюнкцией и инверсией. Это основные логические операции, при помощи которых можно записать любую логическую функцию.

1. Логическая операция ИНВЕРСИЯ (ОТРИЦАНИЕ) Ш Ш Ш соответствует частице НЕ обозначается черточкой над именем переменной или знаком ¬ перед переменной Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна. Таблица истинности инверсии имеет вид: A 0 1 1 0

2. Логическая операция ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ) Ш соответствует союзу ИЛИ Ш обозначается знаком или ║ Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. А В С =0, только если А=0, В=0, С=0. Таблица истинности дизъюнкции имеет следующий вид: Ш v + v v A B АVВ 0 0 1 1 1 0 1 1

3. Логическая операция КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ) Ш Ш Ш соответствует союзу И обозначается знаком & или Λ, или · Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны. Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. А & В & С=1, только если А=1, В=1, С=1. Таблица истинности конъюнкции имеет следующий вид: A B А&В 0 0 1 1 1

ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ n Сложные высказывания можно записывать в виде формул. Для этого простые логические высказывания нужно обозначить как логические переменные буквами и связать их с помощью знаков логических операций. Такие формулы называются логическими выражениями. Например: n Чтобы определить значение логического выражения необходимо подставить значения логических переменных в выражение и выполнить логические операции. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке: 1. инверсия; 2. конъюнкция; 3. дизъюнкция; 4. импликация и эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.

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

Например, построим таблицу истинности для логической функции: Количество входных переменных в заданном выражении равно трем (A, B, C). Значит, количество входных наборов, а значит и строк Q=23=8. Количество столбцов равно 6 (3 переменные + 3 операции). Столбцы таблицы истинности соответствуют значениям исходных выражений A, B, C, промежуточных результатов и (B V C), а также искомого окончательного значения сложного арифметического выражения

A B C BVC 0 0 0 1 1 0 1 1 1 0 0 0 1 0 1 1 0 0 1 1 1 0 Задание. Постройте таблицу истинности для данного логического выражения:

А В 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 Равносильные логические выражения. Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак =. Например:

ЗАПИСЬ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ ИСТИННОСТИ Правила построения логического выражения: 1. Для каждой строки таблицы истинности с единичным значением функции построить минтерм. Минтермом называется произведение, в котором каждая переменная встречается только один раз - либо с отрицанием, либо без него. Переменные, имеющие нулевые значения в строке, входят в минтерм с отрицанием, а переменные со значением 1 - без отрицания. 2. Объединить все минтермы операцией дизъюнкция (логическое сложение), что даст стандартную сумму произведений для заданной таблицы истинности.

X 2 X 3 F 0 0 0 1 1 0 1 0 1 0 0 1 Построим логическое выражение для F. Найдем строки, в которых F=1. Это вторая, третья и шестая. X 1 1 Пример. Дана таблица истинности: 1 1 0 Для второй строки X 1=0, Х 2=0, X 3=1. Эту строку описывает минтерм Для третьей строки X 1=0, Х 2=1, X 3=0. Эту строку описывает минтерм Для шестой строки X 1=1, X 2=0, X 3=1. Эту строку описывает минтерм Объединяя термы, получим булево выражение F = В это выражение вошли термы произведения для строк с единичным значением функции F, а вся сумма соответствует совокупности из трех строк. Для остальных пяти наборов значений входных переменных это выражение равно нулю.

Логические функции n n Любое логическое выражение (составное высказывание) можно рассматривать как логическую функцию F(X 1, X 2, . . . , Xn) аргументами которой являются логические переменные X 1, X 2, . . . , Хn (простые высказывания). Сама функция как и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0). Выше были рассмотрены функции двух аргументов: логическое умножение F(A, B) = A&B, логическое сложение F(A, B) = AVB, а также логическое отрицание F(A) = ¬А, в котором значение второго аргумента можно считать равным нулю. Каждая логическая функция двух аргументов имеет четыре возможных набора значений аргументов. Может существовать N = 24 = 16 различных логических функций двух аргументов. Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности:

Аргументы Логические функции А В F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 F 12 F 13 F 14 F 15 F 16 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 Легко заметить, что здесь логическая функция F 2 является функцией логического умножения, F 8 - функцией логического сложения, F 13 - функцией логического отрицания для аргумента А и F 11 - функцией логического отрицания для аргумента В. F 1(A, B) = 0 константа нуль, F 16(A, B) = 1 константа единица. F 4=A, F 6=B, F 7 – сложение по модулю 2, F 10 – эквивалентность. F 9 – инвертированная дизъюнкция (стрелка Пирса), F 15 – инвертированная конъюнкция (штрих Шеффера), F 14 – импликация.

ИМПЛИКАЦИЯ (ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ). n n n Импликация двух высказываний А и В соответствует союзу «ЕСЛИ…ТО» . Она обозначается символом → Запись А → В читается как «из А следует В» В обычной логике это очень важная функция. Она отражает причинно следственную связь, хотя и не строгую. Говорят «х1 имплицирует (влечет) х2» Импликация двух высказываний истинна всегда, кроме случая, если первое высказывание истинно, а второе ложно. Таблица истинности импликации двух суждений А и В такова: А В А→В 0 0 1 1 1 В программировании эту операцию обозначают «IMP» .

Src="https://сайт/presentation/-76620620_344623301/image-26.jpg" alt="ЭКВИВАЛЕНТНОСТЬ (ЛОГИЧЕСКОЕ РАВЕНСТВО, ФУНКЦИЯ ТОЖДЕСТВА) n n Она обозначается символами ≡ или . ("> ЭКВИВАЛЕНТНОСТЬ (ЛОГИЧЕСКОЕ РАВЕНСТВО, ФУНКЦИЯ ТОЖДЕСТВА) n n Она обозначается символами ≡ или. («тогда и только тогда»). Запись А ≡ В читается как «А эквивалентно В» . Эквивалентность двух высказываний истинна только в тех случаях, когда оба высказывания ложны или оба истинны. Таблица истинности эквивалентности двух суждений А и В такова: А В А≡В 0 0 1 0 1 0 0 1 1 1 В программировании эту операцию обозначают «EQV» . В алгебре высказываний все логические функции могут быть сведены путём логических преобразований к трём базовым логическим операциям: инверсии, дизъюнкции и конъюнкции

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

1. Закон тождества. Всякое высказывание тождественно самому себе: Этот закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует. 2. Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А - истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: Закон непротиворечия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”

3. Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означа ет, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание. 4. Закон двойного отрицания. Если дважды отрицать неко торое высказывание, то в результате мы получим исходное высказывание: Закон двойного отрицания. Отрицать отрицание какого нибудь высказывания то же, что утверждать это высказывание. “ Неверно, что 2× 2¹ 4”

5. Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых «сомножителей» равносильна одному из них: Дизъюнкция одинаковых «слагаемых» равносильна одному: 6. Законы де Моргана: Смысл законов де Моргана (Август де Морган (1806 1871) шотландский математик и логик) можно выразить в кратких словесных формулировках: отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых; отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

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

9. Правило дистрибутивности. В отличие от обычной алгеб ры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки, как общие множители, так и общие слагаемые: Дистрибутивность умножения относительно сложения: Дистрибутивность сложения относительно умножения: 10. 11. 12. Законы поглощения:

ЗАДАЧА 1. Разбирается дело Лёнчика, Пончика и Батончика. Кто то из них нашел и утаил клад. На следствии каждый из них сделал по два заявления. Батончик: «Я не делал этого. Пончик сделал это» Лёнчик: «Пончик не виновен. Батончик сделал это» Пончик: «Я не делал этого. Лёнчик не делал этого» Суд установил, что один из них дважды солгал, другой - дважды сказал правду, третий - один раз солгал, один раз сказал правду. Кто утаил клад? Решение: Введём обозначения: Б –клад утаил Батончик, П клад утаил Пончик, Л клад утаил Лёнчик. Рассмотрим три возможных варианта – виноват Батончик, виноват Пончик, виноват Лёнчик. При таких вариантах получаем следующие значения высказываний трёх обвиняемых. Высказывания Батончика Возможные варианты Высказывания Лёнчика Высказывания Пончика Соответствие условию задачи Б Л П ¬Б П ¬П Б ¬П ¬Л 1 0 0 1 1 - 0 0 1 1 1 0 0 0 1 + 0 1 0 1 0 - В первом варианте один солгал дважды, а двое сказали правду дважды, что не соответствует условию задачи. В третьем варианте все один раз сказали правду и один раз солгали, что также не соответствует условию задачи. Во втором варианте один дважды солгал, другой дважды сказал правду, а третий один раз сказал правду, а один раз солгал, что соответствует условию задачи. Следовательно клад утаил Пончик.

Задача 2. В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях. Один считает, что первой будет Наташа, а Маша будет второй. Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место. Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на чемпионате заняли Наташа, Маша, Люда, Рита? Решение: Введём обозначения: Н 1 – Наташа на 1 месте, М 2 – Маша на 2 месте, Л 2 – Люда на 2 месте, Р 4 – Рита на 4 месте, Р 3 – Рита на 3 месте, Н 2 – Наташа на 2 месте. Занесём возможные варианты высказываний трёх болельщиков в таблицу с учётом того, что каждый из болельщиков оказался прав только в одном из своих прогнозов: Высказывания 1 -ого болельщика Высказывания 2 -ого болельщика Соответствие условию задачи Н 1 М 2 Л 2 Р 4 Р 3 Н 2 0 1 0 1 - 0 1 1 0 0 1 - 1 0 0 1 1 0 - 1 0 0 1 - 1 0 1 0 + Из анализа таблицы видно, что условию задачи соответствует только последняя строка, значит первое место заняла Наташа, второе – Люда, третье – Рита, а Маша –четвёртое.

Задача 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей? Решение: Введём обозначения: ВК – Вадим изучает китайский язык, СК – Сергей изучает китайский язык, МА Михаил изучает арабский язык. Занесём в таблицу возможные варианты значений высказываний с учётом условия задачи, что одно из утверждений верно, а два ложны: ВК ¬ СК ¬ МА ВК СК МА Соответствие условию задачи 1 0 0 1 1 1 - 0 0 1 0 + 0 1 0 0 0 1 - Возможные варианты высказываний Проанализируем строки в трёх последних столбцах. Условию задачи соответствует только вторая строка, значит Сергей изучает китайский язык, Михаил – японский (так как он не изучает арабский), тогда Вадим изучает арабский язык.

Задача 4. Три одноклассника - Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего - регби. Юра сказал, что на туризм ему не хватает времени, хотя его сестра - единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен. Определите, кто чем любит заниматься в свободное время и у кого какая профессия. Решение: Здесь исходные данные разбиваются на тройки (имя - профессия - увлечение). Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист. Имя Юра Профессия врач Увлечение туризм Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач - Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени - Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем: Имя Юра Тимур Влад Профессия физик врач юрист Увлечение бег туризм регби Ответ. Влад - юрист и регбист, Тимур - врач и турист, Юра - физик и бегун.

Задачи для самостоятельного решения Задача 1. Трое друзей, болельщиков автогонок "Формула 1", спорили о результатах предстоящего этапа гонок. - Вот увидишь, Шумахер не придет первым, - сказал Джон. Первым будет Хилл. - Да нет же, победителем будет, как всегда, Шумахер, - воскликнул Ник. - А об Алези и говорить нечего, ему не быть первым. Питер, к которому обратился Ник, возмутился: - Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину. По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки? Задача 2. В спортивных соревнованиях принимали участие пять команд: "Вымпел", "Метеор", "Нептун", "Старт" и "Чайка". Об их итогах соревнования имеется пять высказываний: 1) Второе место занял "Вымпел", a "Cтарт" оказался на третьем. 2) Хорошо выступала команда "Нептун", она стала победителем, а "Чайка" вышла на второе место. 3) Да нет же, "Чайка" заняла только третье место, а "Нептун" был последним. 4) Первое место по праву завоевал "Cтарт", а "Метеор" был 4 м. 5) Да, "Метеор", действительно, был четвертым, а "Вымпел" был 2 м. Известно, что команды не делили места между собой и что в каждом высказывании одно утверждение правильное, а другое нет. Как распределились места между командами? Задача 3 Три дочери писательницы Дорис Кей - Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств - пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что: Джуди живет не в Париже, а Линда - не в Риме; парижанка не снимается в кино; та, кто живет в Риме, певица; Линда равнодушна к балету. Где живет Айрис, и какова ее профессия?

Логические элементы В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Знания из области математической логики можно использовать для конструирования различных электронных устройств. Нам известно, что 0 и 1 в логике не просто цифры, а обозначение состояний какого то предмета нашего мира, условно называемых "ложь" и "истина". Таким предметом, имеющим два фиксированных состояния, может быть электрический ток. Были созданы устройства управления электричеством электронные схемы, состоящие из набора полупроводниковых элементов. Такие электронные схемы, которые преобразовывают сигналы только двух фиксированных напряжений электрического тока стали называть логическими элементами. Логические элементы - это электронные устройства, которые преобразуют проходящие через них двоичные электрические сигналы по определенному закону. Логические элементы имеют один или несколько входов, на которые подаются электрические сигналы, обозначаемые условно 0, если отсутствует электрический сигнал, и 1, если имеется электрический сигнал. Также логические элементы имеют один выход, с которого снимается преобразованный электрический сигнал. Было доказано, что все электронные схемы компьютера могут быть реализованы с помощью трёх базовых логических элементов И, ИЛИ, НЕ.

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

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

Логический элемент И (конъюнктор) Логический элемент, выполняющий логическое умножение, называется конъюнктор. Он имеет, как минимум, два входа. На функциональных схемах он обозначается: На выходе этого элемента будет сигнал 1 только в том случае, когда на все входы поступает сигнал 1. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль. выход вход 1 вход 2 0 0 1 1 1 Другие логические элементы построены из трех простейших базовых элементов и выполняют более сложные логические преобразования информации.

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

Функциональные схемы Сигнал, выработанный одним логическим элементом, можно подавать на вход другого элемента, это дает возможность образовывать цепочки из отдельных логических элементов - функциональные схемы. Функциональная (логическая) схема – это схема, состоящая из логических элементов, которая выполняет определённую функцию. Анализируя функциональную схему, можно понять, как работает логическое устройство, т. е. дать ответ на вопрос: какую функцию она выполняет. Важной формой описания функциональных схем является структурная формула. Покажем на примере, как выписывают формулу по заданной функциональной схеме. Ясно, что элемент “И” осуществляет логическое умножение значений ¬А и В. Над результатом в элементе “НЕ” осуществляется операция отрицания, т. е. вычисляется значение выражения: Таким образом структурной формулой данной функциональной схемы является формула:

Таблица истинности функциональной схемы Для функциональной схемы можно составить таблицу истинности, то есть таблицу значений сигналов на входах и выходах схемы, по которой можно понять какую функцию выполняет данная схема. Таблица истинности - это табличное представление логической (функциональной) схемы в котором перечислены все возможные сочетания значений входных сигналов вместе со значением выходного сигнала для каждого из этих сочетаний. Составим таблицу истинности для данной логической схемы: Начертим таблицу: количество столбцов = количество входов + количество выходов, количество строк = 2 количество входов. В данной таблице 3 столбца и 4 строки. Заполним первые столбцы всеми возможными вариантами входных сигналов А (вход 1) В (вход 2) 0 0 0 1 1 С (выход)

Рассмотрим первый вариант входных сигналов: А=0, В=0. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу. Рассмотрим второй вариант входных сигналов: А=0, В=1. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=0), запишем в таблицу. Рассмотрим третий вариант входных сигналов: А=1, В=0. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу.

Рассмотрим четвёртый вариант входных сигналов: А=1, В=1. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу. В результате получаем таблицу истинности данной логической схемы: А (вход 1) В (вход 2) С (выход) 0 0 1 0 1 1 1 1 Задание. Построить таблицу истинности для данной логической схемы и записать формулу для данной схемы:

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

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

Задание. Построить логическую схему для заданной таблицы истинности: С F 0 0 0 1 1 1 0 0 0 1 0 1 Построим логическую схему для данного выражения: В 0 Упростим полученное логическое выражение: А 0 Запишем логическую функцию по данной таблице истинности: 1 0 0 1 1

Попробуем, действуя по этому плану, сконструировать устройство для сложения двух двоичных чисел (одноразрядный полусумматор). Пусть нам необходимо сложить двоичные числа А и В. Через P и S обозначим первую и вторую цифру суммы: A + B = PS. Вспомните таблицу сложения двоичных чисел. 1. Таблица истинности, определяющая результат сложения, имеет вид: Слагаемые Перенос Сумма А В Р S 0 0 0 1 1 0 2. Сконструируем функции P(A, B) и S(A, B) по этой таблице: Преобразуем вторую формулу, пользуясь законами логики:

3. Теперь можно построить функциональную схему одноразрядного полусумматора: Чтобы убедиться в том, как работает схема, проследите за прохождением сигналов в каждом из четырёх случаев и составьте таблицу истинности данной логической схемы. Условное обозначение одноразрядного сумматора:

Полный одноразрядный сумматор. Одноразрядный двоичный сумматор на три входа и два выхода называется полным одноразрядным сумматором. Логика работы одноразрядного сумматора на три входа или полного сумматора приведена в таблице, где А, В суммируемые двоичные цифры, Pо перенос из младшего разряда, S образующаяся сумма данного разряда и осуществляет перенос P в следующий старший разряд. Слагаемые Перенос из младшего разряда Сумма Перенос А B P 0 S P 0 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 1 Формула переноса: Формула для вычисления суммы:

После преобразования формулы переноса и суммы принимают вид: Теперь можно построить схему полного одноразрядного сумматора с учётом переноса из младшего разряда.

Сумматор это электронная логическая схема, выполняющая суммирование двоичных чисел поразрядным сложением. Сумматор является центральным узлом арифметико логического устройства процессора. Находит он применение и в других устройствах компьютера. В реальных электронных схемах сумматор изображается так: Сумматор выполняет сложение многозначных двоичных чисел. Он представляет собой последовательное соединение одноразрядных двоичных сумматоров, каждый из которых осуществляет сложение в одном разряде. Если при этом возникает переполнение разряда, то перенос суммируется с содержимым старшего соседнего разряда. На рисунке показано, как из N сумматоров можно составить устройство для сложения двух N разрядных двоичных кодов, это схема многоразрядного сумматора.

ТРИГГЕР Триггер электронная схема, применяемая для хранения значения одноразрядного двоичного кода. Воздействуя на входы триггера, его переводят в одно из двух возможных состояний (0 или 1). С поступлением сигналов на входы триггера в зависимости от его состояния либо происходит переключение, либо исходное состояние сохраняется. При отсутствии входных сигналов триггер сохраняет свое состояние сколь угодно долго. Термин триггер происходит от английского слова trigger защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает "хлопанье". Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить ("перебрасываться") из одного электрического состояния в другое. Существуют разные варианты исполнения триггеров в зависимости от элементной базы (И НЕ, ИЛИ НЕ) и функциональных связей между сигналами на входах и выходах (RS, JK, T, D и другие). Самый распространённый тип триггера это RS триггер (S и R соответственно от английских set установка, и reset сброс). Условное обозначение RS триггера:

RS триггер построен на 2 х логических элементах: ИЛИ НЕ либо И – НЕ. Как, правило, триггер имеет 2 выхода: прямой и инверсный Q Как он работает? Пусть на вход элемента № 1 подан сигнал 1, а на вход элемента № 3 0. На выходе элемента № 1 независимо от того, какой второй сигнал поступит на вход, будет 1, т. к. это элемент ИЛИ (по свойствам дизъюнкции). Пройдя через элемент № 2 сигнал примет значение 0 (Q=0). Следовательно, и на втором входе элемента № 3 установится сигнал 0. На выходе элемента № 3 0. Пройдя через элемент № 4 сигнал изменится на 1. Следовательно, = 1. Убедимся, что данное устройство сохраняет информацию. Запомните, что S=0, R=1, Q=0, =1. В момент прекращения входных сигналов (S=0, R=0) на выходе =1. Это напряжение подается на вход элемента № 1. На выходе элемента № 1 сохраняется 1, и на Q сигнал 0. На входах элемента № 3 0, следовательно =1. Таким образом, при отсутствии на внешних входах сигналов 1 триггер поддерживает постоянное напряжение на своих выходах. Чтобы изменить напряжение на выходах триггера, надо подать сигнал 1 на вход элемента № 3. Тогда Q=1, =0.

RS триггер Вход Выход Режим работы S R Q 0 0 Хранение 1 0 Запись 1 0 1 Запись 0 1 1 Х Х Запрещение ()

РЕГИСТРЫ Функциональная схема компьютера, состоящая из триггеров, предназначенная для запоминания многоразрядных кодов и выполнения над ними некоторых логических преобразований называется регистром. Упрощенно регистр можно представить как совокупность ячеек, в каждой из которых может быть записано одно из двух значений: 0 или 1, то есть один разряд двоичного числа. С помощью регистров можно выполнять следующие операции: установку, сдвиг, преобразование. Основными типами регистров являются параллельные и последовательные (сдвигающие). Совокупность регистров, используемых ЭВМ для запоминания программы работы, исходных и промежуточных результатов называется оперативной памятью (ОП). Регистры содержатся в различных вычислительных узлах компьютера процессоре, периферийных устройствах и т. д. Регистр это устройство, предназначенное для хранения многоразрядного двоичного числового кода, которым можно представлять и адрес, и команду, и данные.

РЕГИСТРЫ Существует несколько типов регистров, отличающихся видом выполняемых операций. Некоторые важные регистры имеют свои названия, например: сдвиговый регистр предназначен для выполнения операции сдвига; счетчики схемы, способные считать поступающие на вход импульсы. К ним относятся Т триггеры (название от англ. tumble опрокидываться). Этот триггер имеет один счетный вход и два выхода. Под действием сигналов триггер меняет свое состояние с нулевого на единичное и наоборот. Число перебрасываний соответствует числу поступивших сигналов; счетчик команд регистр устройства управления процессора (УУ), содержимое которого соответствует адресу очередной выполняемой команды; служит для автоматической выборки программы из последовательных ячеек памяти; регистр команд регистр УУ для хранения кода команды на период времени, необходимый для ее выполнения. Часть его разрядов используется для хранения кода операции, остальные для хранения кодов адресов операндов. В ЭВМ применяются регистры 8, 16, 32, 48 и 64 разрядов.

ШИФРАТОРЫ И ДЕШИФРАТОРЫ Шифратор и дешифратор являются типовыми узлами ЭВМ. Шифратор (кодер) это логическое устройство, которое преобразует единичный сигнал на одном из входов в n-разрядный двоичный код. Наибольшее применение он находит в устройствах ввода информации (например в клавиатуре), для преобразования десятичных чисел в двоичную систему счисления. Дешифратор (декодер) это логическое устройство, преобразующее двоичный код, поступающий на его входы, в сигнал только на одном из его выходов. Дешифраторы широко применяются в устройствах управления, в системах цифровой индикации с газоразрядными индикаторами, для построения распределителей импульсов по различным цепям и т. д. Схема используется для перевода двоичных цифр в десятичные. Дешифратор двоичного n разрядного кода имеет 2 n выходов, т. к. каждому из 2 n значений входного кода должен соответствовать единичный сигнал на одном из выходов дешифратора.

Формы мышления

Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания.

Логика - это наука о формах и способах мышления.

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

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

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

Понятие - это форма мышления, фиксирующая основные, существенные признаки объекта.

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

Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.

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

Высказывания могут быть выражены не только с помощью естественных языков, но и с помощью формальных языков. Например, высказывание на естественном языке имеет вид «Два умножить на два равно четырем», а на формальном, математическом языке оно записывается в виде «2x2 = 4».

Об объектах можно судить верно или неверно, т.е. высказывание может быть истинным или ложным. Истинным будет высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Примером истинного высказывания может служить следующее: «Процессор является устройством обработки информации».

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

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

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

и отношениях между ними. Высказывание может быть либо истинно,

либо ложно.

Высказывание не может быть выражено повелительным или вопросительным предложением, так как оценка их истинности или ложности невозможна.

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

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

Приведенное выше составное высказывание истинно, так как истинны входящие в него простые высказывания.

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

Например, если мы имеем суждение «Все углы треугольника равны», то мы можем путем умозаключения доказать, что в этом случае справедливо суждение «Этот треугольник равносторонний».

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

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

Контрольные вопросы и задания

1. Какие существуют основные формы мышления? Приведите примеры

понятий, суждений и умозаключений.

• 2. В чем состоит разница между содержанием и объемом понятия?
• 3. Может ли быть высказывание выражено в форме вопросительного предложения?
• 4. Как определяется истинность или ложность простого высказывания?

Составного высказывания?

ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

ФОРМЫ МЫШЛЕНИЯ

• ЛОГИКА - это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений.

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

• Формальная логика связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком. Математическая логика изучает только умозаключения со строго определенными объектами и суждениями, для которых можно однозначно решить, истинны они или ложны.

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

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

Основные формы мышления

• Основными формами мышления являются: ПОНЯТИЯ, СУЖДЕНИЯ, УМОЗАКЛЮЧЕНИЯ.

• ПОНЯТИЕ - форма мышления, в которой отражаются существенные признаки отдельного объекта или класса однородных объектов. Примеры: портфель, трапеция, ураганный ветер.

• Понятие имеет две стороны: содержание и объем.

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

• Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.

• СУЖДЕНИЕ – это форма мышления, в которой что-либо утверждается или отрицается об объектах, их свойствах и отношениях.

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

• «Берн - столица Франции»,

• «Река Кубань впадает в Азовское море»,

• «2>9», «3×5=10»

• УМОЗАКЛЮЧЕНИЕ – это форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем новое суждение (заключение).

• Все металлы - простые вещества. Литий - металл.→ Литий - простое вещество.

• Один из углов треугольника равен 90º. → Этот треугольник прямоугольный.

АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

Английский математик Джордж Буль (1815 - 1864 г.) создал логическую алгебру, в которой высказывания обозначены буквами. Сочинение Джорджа Буля, в котором подробно исследовалась эта алгебра, было опубликовано в 1854 г. Оно называлось «Исследование законов мысли» («Investigation of the Laws of Thought»). Отсюда ясно, что Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления, то есть законов логики. Алгебру логики иначе называют алгеброй высказываний. В математической логике суждения называются высказываниями.

ВЫСКАЗЫВАНИЕ - это повествовательное предложение, о котором можно сказать, что оно или истинно или ложно.

• Например: Земля - планета Солнечной системы . (Истинно) 2+8 (Ложно) 5 · 5=25 (Истинно) Всякий квадрат есть параллелограмм (Истинно) Каждый параллелограмм есть квадрат (Ложно) 2 · 2 =5 (Ложно)

Не всякое предложение является высказыванием: 1) Восклицательные и вопросительные предложения высказываниями не являются. - “Какого цвета этот дом?” - “Пейте томатный сок!” - “Стоп!” 2) Не являются высказываниями и определения. “Назовем медианой отрезок, соединяющий вершину треугольника с серединой противоположной стороны”. Определения не бывают истинными или ложными, они лишь фиксируют принятое использование терминов. 3) Не являются высказываниями и предложения типа “Он сероглаз” или

• “х- 4х + 3=0” - в них не указано о каком человеке идет речь или для какого числа х верно равенство. Такие предложения называются высказывательными формами.

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

.

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

• Простые высказывания назвали логическими переменными и для простоты записи их обозначают латинскими буквами: А, В, С… Луна является спутником Земли . А = 1 Москва – столица Германии . В = 0

• Сложные высказывания называются логическими функциями . Значения логической функции также может принимать значения только 0 или 1.

БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

• В алгебре высказываний, как и в обычной алгебре, вводится ряд операций. Логические связки И, ИЛИ и НЕ заменяются логическими операциями: конъюнкцией, дизъюнкцией и инверсией. Это основные логические операции, при помощи которых можно записать любую логическую функцию.

1. Логическая операция ИНВЕРСИЯ (ОТРИЦАНИЕ)

• соответствует частице НЕ

• обозначается черточкой над именем переменной или знаком ¬ перед переменной

• Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

• Таблица истинности инверсии имеет вид:

2. Логическая операция ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ )

• соответствует союзу ИЛИ

• обозначается знаком v или + или ║

• Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. А v В v С =0, только если А=0, В=0, С=0. Таблица истинности дизъюнкции имеет следующий вид:

3. Логическая операция КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ)

• соответствует союзу И

• обозначается знаком & или Λ, или ·

• Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны. Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. А & В & С=1, только если А=1, В=1, С=1. Таблица истинности конъюнкции имеет следующий вид:

ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ

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

Чтобы определить значение логического выражения необходимо подставить значения логических переменных в выражение и выполнить логические операции. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке: 1. инверсия; 2. конъюнкция; 3. дизъюнкция; 4. импликация и эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.

Таблицы истинности

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

• При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий:

• 1) записать выражение и определить порядок выполнения операций

• 2) определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (определяется по формулеQ=2n , где n - количество входных переменных)

• 3) определить количество столбцов в таблице истинности (= количество логических переменных + количество логических операций)

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

• 5) заполнить таблицу истинности, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности

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

• Например, построим таблицу истинности для логической функции:

Количество входных переменных в заданном выражении равно трем (A,B,C) . Значит, количество входных наборов, а значит и строк Q=23=8 . Количество столбцов равно 6 (3 переменные + 3 операции). Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C , промежуточных результатов и (B V C ), а также искомого окончательного значения сложного арифметического выражения

ЗАПИСЬ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ ИСТИННОСТИ

• Правила построения логического выражения:

• 1. Для каждой строки таблицы истинности с единичным значением функции построить минтерм . Минтермом называется произведение, в котором каждая переменная встречается только один раз - либо с отрицанием, либо без него. Переменные, имеющие нулевые значения в строке, входят в минтерм с отрицанием, а переменные со значением 1 - без отрицания.

• 2. Объединитьвсе минтермы операцией дизъюнкция (логическое сложение), что даст стандартную сумму произведений для заданной таблицы истинности.

Логические функции

• Любое логическое выражение (составное высказывание) можно рассматривать как логическую функцию F(X1,X2, ..., Xn ) аргументами которой являются логические переменные X1, X2, ..., Хn (простые высказывания). Сама функция как и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0).

• Выше были рассмотрены функции двух аргументов: логическое умножение F(A,B) = A&B, логическое сложение F(A,B) = AVB, а также логическое отрицание F(A) = ¬А, в котором значение второго аргумента можно считать равным нулю.

• Каждая логическая функция двух аргументов имеет четыре возможных набора значений аргументов. Может существовать N = 24 = 16 различных логических функций двух аргументов.

• Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности:

ИМПЛИКАЦИЯ (ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ).

• Импликация двух высказываний А и В соответствует союзу «ЕСЛИ…ТО». Она обозначается символом →

• Запись А → В читается как «из А следует В»

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

• Таблица истинности импликации двух суждений А и В такова:

ЭКВИВАЛЕНТНОСТЬ (ЛОГИЧЕСКОЕ РАВЕНСТВО, ФУНКЦИЯ ТОЖДЕСТВА)

• Она обозначается символами ≡ или. («тогда и только тогда»).

• Запись А ≡ В читается как «А эквивалентно В».

• Эквивалентность двух высказываний истинна только в тех случаях, когда оба высказывания ложны или оба истинны.

• Таблица истинности эквивалентности двух суждений А и В такова:

Логические законы и правила преобразования логических выражений

• Равносильности формул логики высказываний часто называют законами логики . Законы логики отражают наиболее важные закономерно­сти логического мышления.

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

1. Закон тождества. себе:

• 1. Закон тождества. Всякое высказывание тождественно самомусебе:

• Этот закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

• 2. Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А - истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должнобыть ложно:

• Закон непротиворечия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”

• 3. Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означа­ет, что результат логического сложения высказывания и его отрицания всегда принимает значение истина:

• Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано.

• “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

• 4. Закон двойного отрицания. Если дважды отрицать неко­торое высказывание, то в результатемы получим исходное высказывание:

• Закон двойного отрицания.Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. “ Неверно, что 2× 2¹ 4”

5. Законы идемпотентности.

• 5. Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов.

• Конъюнкция одинаковых «сомножителей» равносильна одному из них:

• Дизъюнкция одинаковых «слагаемых» равносильна одному:

• 6. Законы де Моргана:

• Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках: отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых;

• отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

7. Правило коммутативности. логического умноженияи логического сложения:

• 7. Правило коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказыва­ний можноменять местами логические переменные при опе­рацияхлогического умноженияи логического сложения:

• Логическое умножение:

• Логическое сложение:

• 8. Правило ассоциативности. Если в логическом выраже­нии используются только операция логического умножения или только операция логического сложения, то можно пре­небрегать скобками или произвольно их расставлять:

• Логическое умножение:

• Логическое сложение:

9. Правило дистрибутивности. общие слагаемые:

• 9. Правило дистрибутивности. В отличие от обычной алгеб­ры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки, как общие множители, так иобщие слагаемые:

• Дистрибутивность умножения относительно сложения:

• Дистрибутивность сложения относительно умножения:

• 12. Законы поглощения:

РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ

ЗАДАЧА 1.

• ЗАДАЧА 1.

• Разбирается дело Лёнчика, Пончика и Батончика. Кто-то из них нашел и утаил клад. На следствии каждый из них сделал по два заявления.

• Батончик: «Я не делал этого. Пончик сделал это»

• Лёнчик: «Пончик не виновен. Батончик сделал это»

• Пончик: «Я не делал этого. Лёнчик не делал этого»

• Суд установил, что один из них дважды солгал, другой - дважды сказал правду, третий - один раз солгал, один раз сказал правду. Кто утаил клад?

Задачи для самостоятельного решения

ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

Логические элементы

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

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

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

• Логические элементы имеют один или несколько входов, на которые подаются электрические сигналы, обозначаемые условно 0 , если отсутствует электрический сигнал, и 1 , если имеется электрический сигнал.

• Также логические элементы имеют один выход, с которого снимается преобразованный электрический сигнал.

• Было доказано, что все электронные схемы компьютера могут быть реализованы с помощью трёх базовых логических элементов И, ИЛИ, НЕ.

Логический элемент НЕ (инвертор)

Логический элемент ИЛИ (дизъюнктор)

Логический элемент И (конъюнктор)

Функциональные схемы

Таблица истинности функциональной схемы

Логическая реализация типовых устройств компьютера

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

• Выясним, как из логических элементов разрабатываются логические устройства.

Этапы конструирования логического устройства.

• Конструирование логического устройства состоит из следующих этапов:

• 1. Построение таблицы истинности по заданным условиям работы проектируемого узла (т.е. по соответствию его входных и выходных сигналов).

• 2. Конструирование логической функции данного узла по таблице истинности, ее преобразование (упрощение), если это возможно и необходимо.

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

• После этого остается только реализовать полученную схему.

Полный одноразрядный сумматор .

ТРИГГЕР

RS-триггер

RS-триггер