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

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

В русском языке союз «или» используется в двояком смысле.

Например, в предложении Обычно в 8 вечера я смотрю телевизор или пью чай союз «или» взят в неисключающем (объединительном) смысле, так как вы можете только смотреть телевизор или только пить чай, но вы можете также пить чай и смотреть телевизор одновременно, потому что мама у вас нестрогая. Такая операция называется нестрогой дизъюнкцией. (Если бы мама была строгая, то она разрешила бы или только смотреть телевизор, или только пить чай, но не совмещать прием пищи с просмотром телепередач.)

В высказывании Данный глагол I или II спряжения союз «или» ис
пользуется в исключающем (разделительном) смысле. Такая операция
называется строгой дизъюнкцией. . ,. ,-> „ ,... > (, г>

Примеры строгих и нестрогих дизъюнкций:

Высказывание	Вид дизъюнкции
Петя сидит на западной или восточной трибуне стадиона	Строгая
Студент едет в электричке или читает книгу	Нестрогая
Оля любит писать сочинения или решать логические задачи	Нестрогая
Сережа учится в школе или окончил ее	Строгая
Завтра дождь будет или не будет (третьего не дано)	Строгая
Давайте бороться за чистоту. Чистота достигается так: или не сорить, или часто убирать	Нестрогая
Зелия движется по круговой или эллиптической орбите	Строгая
Числа можно складывать или перемножать	Нестрогая
Дети бывают или воспитанные, или не наши	?

Обозначение нестрогой дизъюнкции: А ИЛИ В; A OR В; А | В; А V В; А + В. (В данном пособии: А V В.)

Приведем пример дизъюнкции двух простых высказываний.

Допустим, из вашего окна видна автостоянка, на которой обычно стоят две машины: «Мерседес» и «Жигули», но может находиться и какая-то одна из них или не быть ни одной.

Обозначим высказывания:

А = На автостоянке стоит «Мерседес». В = На автостоянке стоят «Жигули».

(А дизъюнкция В) = На автостоянке стоит «Мерседес» или «Жигули».

Глава 3. Логичздуие операции ____________ [___________________________ Щ

Таблица., ^»-«н..;ч; i ■.■;- >i ,;,

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

Мнемоническое правило: дизъюнкция - это логическое сложение, и мы не сомневаемся, что вы заметили, что равенства 0 + 0 = 0; 0+1 = 1;1+0=1, верные для обычного сложения, верны и для операции дизъюнкции, но 1 V 1 = 1.

В слове «конъюнкция» одна буква «и», а в слове «дизъюнкция» две буквы «и», как и в слове «или».

V Л-Символ V (дизъюнкция) образован из первой буквы латинского слова Vel («или»).

«Диз» - «галочка вниз» - V.

В теории множеств дизъюнкции соответствует операция объединения множеств.

Для построения соответствующей объединению множеств диаграммы Эйлера-Венна выберем те строки таблицы истинности, в которых AvB=\. Их три. На диаграмме заштрихуем три области, в которых значения А и В такие же, как в выбранных строках. ^ _ ч."" " * "о L su J I J

30 ___________________________ Часть 1. Элеиснтвьматематичсекой" логики

Графическая иллюстрация: ».*■.

А В A\jB - множество учеников класса, которые являются отличниками или спортсменами.

j Рассмотрим операцию строгой дизъюнкции (исключающее «или»). i Приведем пример строгой дизъюнкции.

,}■ Пусть даны высказывания:

"■ А = На автостоянке стоит «Мерседес».

>; В = На автостоянке стоят «Жигули».

i {А строгая дизъюнкция В) = На автостоянке стоит «Мврседве»*или

«Жигули». v ?;;

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

; . - "4",

Обозначение строгой дизъюнкции: A XOR В; A v В.

глава 3. Логические операции ______________________________________ 31

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

Диаграмма Эйлера - Венна, изображающая строгую дизъюнкцию, строится по таблице истинности таким же способом, как и для остальных логических операций.

Графическая иллюстрация:

<ЗЭ

А - множество отличников в классе; В - множество спортсменов в классе;

А у В - множество учеников класса, которые являются либо отличниками, либо спортсменами.

d "W.C . J

Логическое следование (импликация) -wr™

Логическое следование (импликация) образуется соединением двух!,

высказываний в одно с помощью оборота речи «если ..., то ... ». ■

Примеры импликаций: "

Е = Если клятва дана, то она должна выполняться. {

Р = Если число делится на 9, то оно делится на 3. I

В логике допустимо (принято, договорились) рассматривать и бес-.;:

смысленные с житейской точки зрения высказывания. i

Приведем примеры суждений, которые не только правомерно рассмат-j; ривать в логике, но и которые к тому же имеют значение «истина»:

С = Если коровы летают, то 2 + 2 = 5. Х=Еслия - Наполеон, то у кошки четыре ноги.

Обозначение импликации: А -> В; А =э В. (В данном пособии: А =» В.) Говорят: если А, то В; А имплицирует В; А влечет В; В следует из А.

Часть 1. Элементы математической логики

Глава 3. Логические операций f; Л._________________________ 33

Данная операция не так очевидна, как предыдущие. Объяснить ее можно, например, следующим образом.

Пусть даны высказывания: .>--.< а «<, .<-. *>, w "„ihw

Л А = На улице дождь. >..;; j .„ , | Г,., д

В = Асфальт мокрый. ц

(А импликация 2?) = £Ъш на улице дождь, то асфальт мокрый.

Тогда если идет дождь {А = 1) и асфальт мокрый (5=1), то это соот
ветствует действительности, т. е. истинно. Но если вам скажут, что на
улице идет дождь {А = 1), а асфальт остается сухим (В = 0), то вы посчи
таете это ложью. А вот когда дождя на улице нет (А = 0), то асфальт
может быть и сухим, и мокрым (например, только что проехала поли
вальная машина). ъ. ?; t | rfl ]

Таблица

Форма высказывания: если А, то В,

Г SOW ! ,чи , Т " /1

"? , Л ■ и " . "Л \ и ч > < "Л

Лт С.Ч;":\0«1 "

Поясним построение диаграммы. Нас интересует истинность импликации, поэтому выберем те строки таблицы истинности, в которых А => В = 1. Таких строк три. На диаграмме заштрихуем три области, в которых значения А и В такие же, как в выбранных строках:

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

Разберем один из приведенных выше примеров следований, противоречащих здравому смыслу.

(А = 0)п(В = 0)

(А = 0)п (В = 1)

(Л = 1)п(Я=1)

Логическое равенство (эквивалентность)

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

Часть 1. Элементы математической логики^

Глава 3. Логические операции

Примеры эквивалентностей: "

1) Угол называется прямым тогда и ттько тогда, когда он равен 90°.

2) Две прямые параллельны тогда и только тогда, когда они не пересекаются. .,

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

4) Голова думает тогда и только тогда, когда язык отдыхает. (Шутка.)

Все законы математики, физики, все определения суть эквивалентность высказываний.

Обозначение эквивалентности: А = В; А <=> В; А ~ В. (В данном пособии: А о В.)

Приведем пример эквивалентности. Пусть даны высказывания:

А = Число делится на 3 без остатка (кратно трем). В = Сумма цифр числа делится нацело на 3.

(А эквивалентно В) = Число кратно 3 тогда и только mogda, когда
сумма его цифр делится нацело на 3. , ;

Пояснение:

А	В	А<^В

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

	Значение
	высказывания
Смысл высказываний	Число кратно 3
А и В для указанных < значений "*"	тогда и только тогда, когда
*	сумма его цифр делится нацело на 3
Число не	Сумма цифр не	Истина
кратно трем	кратна трем
Число не	Сумма цифр	Ложь
кратно трем	кратна трем
Число кратно	Сумма цифр не	Ложь
трем	кратна трем
Число кратно	Сумма цифр	Истина
трем	кратна трем

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

В теории множеств этой операции соответствует операция эквивалентности множеств.

Для построения соответствующей эквивалентности множеств диаграммы Эйлера - Венна выберем те строки таблицы истинности, в которых А <=> В = 1. Их две. На диаграмме заштрихуем две области, в которых значения АнВ такие же, как в выбранных строках.

Графическая иллюстрация: c~J_........ 1л ...Li

Ш ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

Инверсия (логическое отрицание) образуется из высказывания с помощью добавления частицы «не» к сказуемому или использования оборота речи «неверно, что...».

Обозначение инверсии: НЕ А; -. A; A; NOT A. >"i, t

Таблица
истинности: ■■■ г -

А	А

Инверсия высказывания истинна, когда выс
казывание ложно, и ложна, когда высказывание
истинно. ■--■

! t ■ .■ " Н ■

Часть 1. Элементы математической логики

Глава 3. Логические операции

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

Обозначение конъюнкции: А Я В; А Л В; А & В; А ■ В; A AND В.

; (Г">* „*

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

Обозначение эквивалентности: А = В; А <=> В; А ~ В.

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

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

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

Обозначение дизъюнкции: А ИЛИ В; А \ В; Л V В; А + В.

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

Импликация (логическое следование) образуется соединением двух высказываний в одно с помощью оборота речи «если..., то...». Обозначение импликации: А-> В;А=$ В.

Опорный конспект «Свойства логических операций»

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

А	В	А^В

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

Ч1я" | ; - VI

. ..,.. . , .-. . if . .................. --,-

■*}■

<Ч. 1

Похожая информация.

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

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

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

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

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

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

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

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

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

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

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

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

Переключательные схемы

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

Вентили, триггеры и сумматоры

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

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

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

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

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

Вентель - это устройство, которое выдает результат булевой операции от введенных в него данных (сигналов).

Простейший вентиль представляет собой транзисторный инвертор, который преобразует низкое напряжение в высокое или наоборот (высокое в низкое). Это можно представить как преобразование логического нуля в логическую единицу или наоборот. Т.е. получаем вентиль НЕ .

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

Выходной сигнал вентиля можно выражать как функцию от входных.

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

Для логических величин обычно используются три операции:

Конъюнкция – логическое умножение (И) – and, &, ∧ .
Дизъюнкция – логическое сложение (ИЛИ) – or, |, v .
Логическое отрицание (НЕ) – not, .

Логические выражения можно преобразовывать в соответствии с законами алгебры логики :

Законы рефлексивности
a ∨ a = a
a ∧ a = a
Законы коммутативности
a ∨ b = b ∨ a
a ∧ b = b ∧ a
Законы ассоциативности
(a ∧ b) ∧ c = a ∧ (b ∧ c)
(a ∨ b) ∨ c = a ∨ (b ∨ c)
Законы дистрибутивности
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Закон отрицания отрицания
(a) = a
Законы де Моргана
(a ∧ b) = a ∨ b
(a ∨ b) = a ∧ b
Законы поглощения
a ∨ (a ∧ b) = a
a ∧ (a ∨ b) = a

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

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

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

Формулу называют элементарной конъюнкцией , если она является конъюнкцией одной или нескольких переменных, взятых с отрицанием или без отрицания. Одну переменную или ее отрицание считают одночленной элементарной конъюнкцией .

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

ДНФ И СДНФ

Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: А1 v А2 v ... v Аn , где каждое Аn - элементарная конъюнкция.

Формула А от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1.А является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х1, х2, …, xk , причем на i-м месте этой конъюнкции стоит либо переменнаяхi либо ее отрицание;
2. Все элементарные конъюнкции в такой ДНФ попарно различны.

Например: А = х1 & НЕ х2 v х1 & х2

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

Она является примером однозначного представления булевой функции в виде формульной (алгебраической) записи.

Теорема о СДНФ

Пусть f(x1 х2, …, хn) – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию f.

Алгоритм построения СДНФ по таблице истинности:

1.В таблице истинности отмечаем наборы переменных, на которых значение функции f = 1.
2.Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
3.Все полученные конъюнкции связываем операциями дизъюнкции.

КНФ И СКНФ

Формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией неповторяющихся элементарных дизъюнкций. КНФ записываются в виде: А1 & А2 & ... & Аn , где каждое Аn – элементарная дизъюнкция.

Формула А от k переменных называется совершенной конъюнктивной нормальной формой (СКНФ), если:
1. А является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных x1, х2, …, хk, причем на i-м месте этой дизъюнкции стоит либо переменная xi, либо ее отрицание;
2. Все элементарные дизъюнкции в такой КНФ попарно различны.

Например: А = (х1 v НЕ х2) & (х1 v х2)

Теорема о СКНФ

Пустьf(x1 х2, …, хn) – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная конъюнктивная нормальная форма, выражающая функцию f.

Алгоритм построения СКНФ по таблице истинности:

1.В таблице истинности отмечаем наборы переменных, на которых значение функции f = 0.
2.Записываем для каждого отмеченного набора дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в дизъюнкцию включаем саму переменную, в противном случае – ее отрицание.
3.Все полученные дизъюнкции связываем операциями конъюнкции.

Из алгоритмов построения СДНФ и СКНФ следует, что если на большей части наборов значений переменных функция равна 0, то для получения ее формулы проще построить СДНФ, в противном случае – СКНФ.

Минимизация логических функций при помощи карт Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

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

Возможность поглощения следует из очевидных равенств

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

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

Метод диаграмм Вейча.

" Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (табл. 4.4.1).

Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. В (табл. 4.4.1) это соответствие показано, В клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (табл. 4.4.2).

Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (табл. 4.4.3).

Таким же образом, т. е. приписыванием еще одной диаграммы 3-х переменных к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко. Для приведенных диаграмм характерно следующее:

Синтез комбинационных схем можно проиллюстрировать решением простой задачи.

Задача 1

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

Решение

С учётом вышеуказанных допущений условие задачи можно однозначно представить в виде таблицы истинности.

Заполнение таблицы осуществляем с учётом того, что функция f является полностью определённой, т.е. она определена на всех возможных наборах переменных x1 - x4. Для n входных переменных существует N = 2n наборов переменных. В нашем примере N = 24 = 16 наборов.

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

Десятичная система счисления

Основание этой системы счисления p равно десяти. В этой системе счисления используется десять цифр. В настоящее время для обозначения этих цифр используются символы 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Число в десятичной системе счисления записывается как сумма единиц, десятков, сотен, тысяч и так далее. То есть веса соседних разрядов различаются в десять раз. Точно также записываются и числа, меньшие единицы. В этом случае разряды числа будут называться как десятые, сотые или тысячные доли единицы.

Рассмотрим пример записи десятичного числа. Для того чтобы показать, что в примере используется именно десятичная система счисления, используем индекс 10. Если же кроме десятичной формы записи чисел не предполагается использования никакой другой, то индекс обычно не используется:

A 10 =247,56 10 =2*10 2 +4*10 1 +7*10 0 +5*10 -1 +6*10 -2 = 200 10 +40 10 +7 10 +0,5 10 +0,06 10

Здесь самый старший разряд числа будет называться сотнями. В приведённом примере сотням соответствует цифра 2. Следующий разряд будет называться десятками. В приведённом примере десяткам соответствует цифра 4. Следующий разряд будет называться единицами. В приведённом примере единицам соответствует цифра 7. Десятым долям соответствует цифра 5, а сотым – 6.

Двоичная система счисления

Основание этой системы счисления p равно двум. В этой системе счисления используется две цифры. Чтобы не выдумывать новых символов для обозначения цифр, в двоичной системе счисления были использованы символы десятичных цифр 0 и 1. Для того чтобы не спутать систему счисления в записи числа используется индекс 2. Если же кроме двоичной формы записи чисел не предполагается использования никакой другой, то этот индекс можно опустить.

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

Рассмотрим пример записи двоичного числа:

A 2 =101110,101 2 = 1*2 5 +0*2 4 +1*2 3 +1*2 2 +1*2 1 +0*2 0 +1*2 -1 +0*2 -2 +1*2 -3 = 32 10 +8 10 +4 10 +2 10 +0,5 10 +0,125 10 =46,625 10

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

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

Восьмеричная система счисления

Основание этой системы счисления p равно восьми. Восьмеричную систему счисления можно рассматривать как более короткий вариант записи двоичных чисел, так как число восемь является степенью числа два. В этой системе счисления используется восемь цифр. Чтобы не выдумывать новых символов для обозначения цифр, в восьмеричной системе счисления были использованы символы десятичных цифр 0, 1, 2, 3, 4, 5, 6 и 7. Для того чтобы не спутать систему счисления в записи числа используется индекс 8. Если же кроме восьмеричной формы записи чисел не предполагается использования никакой другой, то этот индекс можно опустить.

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

Рассмотрим пример записи восьмеричного числа:

A 8 =125,46 8 =1*8 2 +2*8 1 +5*8 0 +4*8 -1 +6*8 -2 = 64 10 +16 10 +5 10 +4 10 /8 10 +6 10 /64 10 = 85,59375 10

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

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

Виды цифровых компараторов

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

Компаратор для сравнения однополярных сигналов

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

Многоразрядные компараторы

Рассмотрим в качестве примера четырехразрядный цифровой компаратор серии К555СП1, восемь входов которого служат для подключения двух четырехразрядных слов: А0 . А3, В0 . B3, подлежащих сравнению. Управляющие входыI(А> В),(А = В) и I(А < В) могут быть использованы для наращивания разрядности компаратора. Предусмотрены три выхода результата сравнения: А> В, А = В и А<В.

Таблица истинности такого компаратора (табл. 1) разбита по строкам на три раздела.

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

Рис. 1. Условное графическое изображение компаратора типа СП1

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

Одноразрядные компараторы

Одноразрядный компаратор имеет два входа на которые одновременно поступают одноразрядные двоичные числа x1 и x2, и три выхода (=, >, <). Из таблицы истинности логические уравнения компаратора при сравнении x1 с x2 получаются в виде

Реализация такого компаратора в базисе И-НЕ приводит к следующему рисунку (рис. 2):

Рисунок 2. Одноразрядный компаратор двоичных чисел.

Таблица 1. Таблица истинности четырехразрядного компаратора типа СП1

Компаратор (аналоговых сигналов) (англ. comparator - сравнивающее устройство ) - электронная схема, принимающая на свои входы два аналоговых сигнала и выдающая логическую «1», если сигнал на прямом входе («+») больше, чем на инверсном входе («−»), и логический «0», если сигнал на прямом входе меньше, чем на инверсном входе.

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

Простейший компаратор представляет собой дифференциальный усилитель. Компаратор отличается от линейного операционного усилителя (ОУ) устройством и входного, и выходного каскадов:

Входной каскад компаратора должен выдерживать широкий диапазон входных напряжений между инвертирующим и неинвертирующим входами, вплоть до размаха питающих напряжений, и быстро восстанавливаться при изменении знака этого напряжения.
Выходной каскад компаратора выполняется совместимым по логическим уровням и токам с конкретным типом входов логических схем (технологий ТТЛ, ЭСЛ и т. п.). Возможны выходные каскады на одиночном транзисторе с открытым коллектором (совместимость с ТТЛ и КМОП логикой).
Для формирования гистерезисной передаточной характеристики компараторы часто охватывают положительной обратной связью. Эта мера позволяет избежать быстрых нежелательных переключений состояния выхода, обусловленном шумами во входном сигнале, при медленно изменяющемся входном сигнале.

При подаче эталонного напряжения сравнения на инвертирующий вход входной сигнал подаётся на неинвертирующий вход, и компаратор является неинвертирующим (повторителем, буфером).

При подаче эталонного напряжения сравнения на неинвертирующий вход входной сигнал подаётся на инвертирующий вход, и компаратор является инвертирующим (инвертором).

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

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

Счетчик импульсов – электронное устройство, предназначенное для подсчета числа импульсов, поданных на вход. Количество поступивших импульсов выражается в двоичной системе счисления.

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

Основными показателями счетчиков являются коэффициент счета К 2n - число импульсов, которое может быть сосчитано счетчиком. Например, счетчик, состоящий из четырех триггеров, может иметь максимальный коэффициент счёта 24=16. Для четырехтриггерного счетчика минимальный выходной код - 0000, максимальный -1111, а при коэффициенте счёта Кс = 10 выходной счет останавливается при коде 1001 = 9.

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

Работу схемы иллюстрируют временные диаграммы, приведенные на рисунке 1, б. При поступлении первого счетного импульса по его спаду первый триггер переходит в состояние Q1 = 1, т.е. в счетчике записан цифровой код 0001. По окончании второго счетного импульса первый триггер переходит в состояние «0», а второй переключается в состояние «1». В счетчике записывается число 2 с кодом 0010.

Рисунок 1 – Двоичный четырехразрядный счетчик: а) схема, б) условно-графическое обозначение, в) временные диаграммы работы

Из диаграммы (рис. 1, б) видно, что, например, по спаду 5-го импульса в счетчике записан код 0101, по 9-му – 1001 и т.п. По окончании 15-го импульса все разряды счетчика устанавливаются в состояние «1», а по спаду 16-го импульса все триггеры обнуляются, т. е. счетчик переходит в исходное состояние. Для принудительного обнуления счетчика имеется вход «сброс».

Коэффициент счета двоичного счетчика находят из соотношения Ксч = 2n, где n - число разрядов (триггеров) счетчика.

Подсчет числа импульсов является наиболее распространенной операцией в устройствах цифровой обработки информации.

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

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

В шифраторе имеется m входов, последовательно пронумерованных десятичным числами (0, 1,2,..., m - 1), и n выходов. Число входов и выходов определяются зависимостью 2n = m (рис. 2, а). Символ «CD» образован из букв, входящих в английское слове Coder.

Подача сигнала на один из входов приводит к появлению на выходах n-разрядного двоичного числа, соответствующего номеру входа. Например, при подаче импульса на 4-й вход на выходах возникает цифровой код 100 (рис. 2, а).

Для обратного преобразования двоичных чисел в небольшие по значению десятичные числа используются дешифраторы (называемые также декодерами). Входы дешифратора (рис. 2, б) предназначаются для подачи двоичных чисел, выходы последовательно нумеруются десятичными числами. При подаче на входы двоичного числа появляется сигнал на определенном выходе, номер которого соответствует входному числу. Например, при подаче кода 110, сигнал появится на 6-м выходе.

Рисунок 2 – а) УГО шифратора, б) УГО дешифратора

Мультиплексор - устройство, в котором выход соединяется с одним из входов, в соответствии с кодом адреса. Т.о. мультиплексор представляет собой электронный переключатель или коммутатор.

Рисунок 3 – Мультиплексор: а) условно-графическое обозначение, б) таблица состояний

На входы А1, А2 подаётся код адреса, определяющий, какой из входов сигналов будет передан на выход устройства (рис. 3).

Для преобразования информации из цифровой формы в аналоговую применяют цифро-аналоговые преобразователи (ЦАП) , а для обратного преобразования - аналого-цифровые преобразователи (АЦП) .

Входной сигнал ЦАП - двоичное многоразрядное число, а выходной - напряжение Uвых, формируемое на основе опорного напряжения.

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

Рисунок 4 – Процесс аналого-цифрового преобразования

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

Регистр – функциональный узел объединяющий несколько однотипных триггеров.

Типы регистров:

1) Регистры защелки – строятся на триггерах защелках (К155ТМ5; К155ТМ7), запись в которые ведется уровнем стробирующего сигнала.

В триггере К155ТМ8 - запись ведется положительным фронтом стробирующего сигнала.

2) Сдвигающие регистры – выполняют функцию только последовательного приема кода.

3) Универсальные регистры – могут принимать информацию в параллельном и последовательном коде.

4) Специальные регистры – К589ИР12 имеют дополнительные варианты использования.

Сдвигающий регистр

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

Таблица 9 Сдвиг кода влево

Универсальные регистры

Они имеют внешние выходы и входы для всех разрядов, а также последовательный вход DS.

Имеются два вида универсальных регистров:

1) регистр выполняющий сдвиг только в одном направлении и параллельный прием кода (например, К155ИР1; К176ИР3).

2) с четырьмя режимами работы: сдвиг вправо/влево; параллельный прием; хранение(например, 8 разрядный регистр К155ИР13; 4 разрядный К500ИР141).

Основной элементарной операцией, выполняемой над кодами чисел в цифровых устройствах, является арифметическое сложение.

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

Сумматоры классифицируют по различным признакам.

В зависимости от системы счисления различают:

двоичные;
двоично-десятичные (в общем случае двоично-кодированные);
десятичные;
прочие (например, амплитудные).

По количеству одновременно обрабатываемых разрядов складываемых чисел:

одноразрядные,
многоразрядные.

По числу входов и выходов одноразрядных двоичных сумматоров:

четвертьсумматоры (элементы "сумма по модулю 2"; элементы "исключающее ИЛИ"), характеризующиеся наличием двух входов, на которые подаются два одноразрядных числа, и одним выходом, на котором реализуется их арифметическая сумма;
полусумматоры, характеризующиеся наличием двух входов, на которые подаются одноименные разряды двух чисел, и двух выходов: на одном реализуется арифметическая сумма в данном разряде, а на другом перенос в следующий (более старший разряд);
полные одноразрядные двоичные сумматоры, характеризующиеся наличием трех входов, на которые подаются одноименные разряды двух складываемых чисел и перенос из предыдущего (более младшего) разряда, и двумя выходами: на одном реализуется арифметическая сумма в данном разряде, а на другом перенос в следующий (более старший разряд).

По способу представления и обработки складываемых чисел многоразрядные сумматоры подразделяются на:

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

Параллельный сумматор в простейшем случае представляет собой n одноразрядных сумматоров, последовательно (от младших разрядов к старшим) соединенных цепями переноса. Однако такая схема сумматора характеризуется сравнительно невысоким быстродействием, так как формирование сигналов суммы и переноса в каждом i-ом разряде производится лишь после того, как поступит сигнал переноса с (i-1)-го разряда.Таким образом, быстродействие сумматора определяется временем распространения сигнала по цепи переноса. Уменьшение этого времени основная задача при построении параллельных сумматоров.

Для уменьшения времени распространения сигнала переноса применяют: конструктивные решения

СВОЙСТВА ЛОГИЧЕСКИХ ОПЕРАЦИЙ

1. Обозначения

1.1. Обозначения для логических связок (операций):

a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);

b) конъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В);

c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В);

d) следование (импликация) обозначается → (например, А → В);

e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);

f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания).

1.2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А /\ В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).

1.3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А \/ В \/ С \/ D означает то же, что и

((¬А) \/ В)\/ (С \/ D).

Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна запись А /\ В /\ С вместо (А /\ В) /\ С.

2. Свойства

Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.

2.1. Общие свойства

Для набора из n логических переменных существует ровно 2 n различных значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2 n строк.

2.2.Дизъюнкция

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

2.3. Конъюнкция

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

2.4. Простые дизъюнкции и конъюнкции

Назовем (для удобства) конъюнкцию простой , если подвыражения, к которым применяется конъюнкция, – различные переменные или их отрицания. Аналогично, дизъюнкция называется простой , если подвыражения, к которым применяется дизъюнкция, – различные переменные или их отрицания.

Простая конъюнкция принимает значение 1 (истина) ровно на одном наборе значений переменных.
Простая дизъюнкция принимает значение 0 (ложь) ровно на одном наборе значений переменных.

2.5. Импликация

Импликация A →B равносильна дизъюнкции (¬ А) \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.
Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A →B истинна при любом значении B.

Конъюнкция: соответствует союзу: «и», обозначается знаком^, обозначает логическое умножение.

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

Таблица истинности для операции «Конъюнкция»:

Таблица №2

Дизъюнкция

Логическая операция соответствует союзу ИЛИ, обозначается знаком v, иначе называется ЛОГИЧЕСКОЕ СЛОЖЕНИЕ.

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

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

A v В v С = 0, только если А = О, В = О, С - 0.

Таблица истинности для операции «Дизъюнкция»:

Таблица №3

Инверсия

Логическая операция соответствует частице не, обозначается ¬ или ¯ и является логическим отрицанием.

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

Таблица истинности для операции «Инверсия»:

Таблица №5

Эквивалентность «А тогда В и только тогда», обозначается А ~ В

Таблица №6

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:

инверсия;

конъюнкция;

дизъюнкция;

импликация и эквивалентность;

Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

Формализация высказываний

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

Земля вращается вокруг своей оси и вокруг Солнца;

орбиты всех планет проходят вокруг Солнца;

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

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

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

Процесс построения информационных моделей с помощью формальных языков называется формализацией.

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

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

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

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

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

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

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

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

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

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

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

Для логических величин обычно используются три операции:

Конъюнкция - логическое умножение (И) - and, &, ∧.

Дизъюнкция - логическое сложение (ИЛИ) - or, |, v.

Логическое отрицание (НЕ) - not,.

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

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

Переключательные схемы

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

Вентили, триггеры и сумматоры

Триггеры и сумматоры - это относительно сложные устройства, состоящие из более простых элементов - вентилей.

Информация и информационные процессы. Виды информации, её двоичное кодирование. Количество информации, подходы к определению понятия «количество информации», единицы измерения информации. Двоичное кодирование числовой, текстовой, графической, звуковой информации

Информация (от лат. informatio — «разъяснение, изложение, осведомлённость») — сведения о чём-либо, независимо от формы их представления.

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

Свойства информации:

Объективность (информация объективна, если она не зависит от чьего-либо мнения, суждения);

Достоверность (информация достоверна, если она отражает истинное положение дел);

Полнота (информация полна, если ее достаточно для понимания и принятия решения);

Актуальность (информация актуальна, своевременна, если она важна, существенна для настоящего времени);

Полезность (оценивается по тем задачам, которые мы можем решить с ее помощью);

Понятность (информация понятна, если она выражена на языке, доступном для получателя);

Доступность (информация доступна, если мы можем её получить).

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

Информация проявляется именно в информационных процессах. Информационные процессы всегда протекают в каких-либо системах (социальных, социотехнических, биологических и пр.).

Наиболее обобщенными информационными процессами являются сбор, преобразование, использование информации.

К основным информационным процессам, изучаемым в курсе информатики, относятся: поиск, отбор, хранение, передача, кодирование, обработка, защита информации.

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

Компьютер является универсальным устройством для автоматизированного выполнения информационных процессов.

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

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

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

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

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

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

Двоичный алфавит состоит из двух цифр 0 и 1.

Цифровые ЭВМ (персональные компьютеры относятся к классу цифровых) используют двоичное кодирование любой информации. В основном это объясняется тем, что построить техническое устройство, безошибочно различающее 2 разных состояния сигнала, технически оказалось проще, чем то, которое бы безошибочно различало 5 или 10 различных состояний.

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