Использование функций алгебры логики

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

Для обозначения   и с т и н о с т и  вводится символ «И» (true, позднее цифра 1), для обозначения   л о ж н о с т и   «Л» (false, позднее 0).

Обозначение логических операций

 («не») – отрицание,

& («И») – конъюнкция (логическое умножение)

V («ИЛИ», «+») – дизъюнкция (логическое сложение)

–> («если то») – импликация,

~ («эквивалентно») – эквивалентность.

В качестве операндов в логических выражениях выступают константы или переменные, которые принимают только два значения: «ИСТИНА» (1) или «ЛОЖЬ» (0).

Простое логическое выражение – выражение, в котором логические переменные и константы (операнды) связаны знаками логических операций. Логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0)

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

Логические операции и таблицы истинности

ОПЕРАЦИЯ ОТРИЦАНИЯ

F = не A

A	не А
0	1
1	0

Логическое отрицание: ИНВЕРСИЯ – если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО

ОПЕРАЦИЯ ЛОГИЧЕСКОГО УМНОЖЕНИЯ

A	B	F
1	1	1
1	0	0
0	1	0
0	0	0

F = A & B.

Логическое умножение КОНЪЮНКЦИЯ – это  выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И.

ОПЕРАЦИЯ ЛОГИЧЕСКОГО СЛОЖЕНИЯ

A	B	F
1	1	1
1	0	1
0	1	1
0	0	0

F = A + B

Логическое сложение – ДИЗЪЮНКЦИЯ – это выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений. Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ.

Логическое следование: ИМПЛИКАЦИЯ – связывает два простых, второе (В) – следствием из этого условия. результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом «следовательно» и выражается словами ЕСЛИ …, ТО …

A	B	F
1	1	1
1	0	0
0	1	1
0	0	1

 

ОПЕРАЦИЯ ЭКВИВАЛЕНТНОСТИ

F = A ~ B

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

Логическая равнозначность: ЭКВИВАЛЕНТНОСТЬ – определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом «эквивалентности» ~.

Порядок выполнения логических операций в сложном логическом выражении:

1. Инверсия.

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

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

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

5. Эквивалентность.

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

Основные законы логики:

А = А              – закон тождества.

А & = 0 – закон непротиворечия (закон выражает тот факт, что высказывание не может быть одновременно истинным и ложным).

A Ú  = 1 – закон исключенного третьего (закон означает, что либо высказывание истинно, либо его отрицание должно быть истинным).

 = А – закон двойного отрицания.

 

СВОЙСТВА КОНСТАНТ

= 1 = 0

А Ú 0 = А А & 0 = 0

А Ú 1 = 1 А & 1 = A

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

А Ú А = А А & А = A

Законы коммутативности:

А Ú В = В Ú А  А & В = В & А

Законы ассоциативности:

А Ú (В Ú С) = (А Ú В) Ú С

А & (В & С) = (А & В) & С

Законы дистрибутивности:

А Ú (В & С) = (А Ú В) & (А Ú С)

А & (В Ú С) = (А & В) Ú (А & С)

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

А Ú (А & В) = А

А & (А Ú В) = А

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

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

Построение таблиц истинности для сложных выражений:

Рассчитаем количество строк и столбцов в таблице. Количество строк = 2ⁿ + две строки для заголовка (n – количество простых высказываний). Количество столбцов = количество переменных + количество логических операций. При построении таблицы надо учитывать все возможные сочетания логических значений 0 и 1 в исходных выражениях. Затем определить порядок действий и составить таблицу с учетом таблиц истинности основных логических операций.

Пример. С оставить таблицу истинности сложного логического выражения D = не A & (B+C).

Решение. А, В, С – три простых высказывания, поэтому

количество строк = 2³ +2 = 10 (n=3, так как на входе три элемента А, В, С)

количество столбцов =6:

1) А;

2) В;

3) С;

4) не A это инверсия А (обозначим Е);

5) B + C это операция дизъюнкции (обозначим F);

6) D = не A & (B+C), т.е. D = E & F это операция конъюнкции.

Таблица 5

Таблица истинности сложного логического выражения

1	2	3	4	5	6
А	В	С	E = не А (не 1)	F = В+С (2+3)	D = E&F (4*5)
1	1	1	0	1	0
1	1	0	0	1	0
1	0	1	0	1	0
1	0	0	0	0	0
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	1	1
0	0	0	1	0	0

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

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

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

конъюнктор

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

дизъюнктор

 

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

Инвертор

ОСНОВЫ КОМПЬЮТЕРНЫХ СЕТЕЙ

Модель сетевого взаимодействия. В 1984 году Международной Организацией по Стандартизации (International Standard Organization, ISO) была разработана модель взаимодействия открытых систем (Open Systems Interconnection, OSI). Модель представляет собой стандарт для проектирования сетевых коммуникаций и предполагает уровневый подход к построению сетей. Каждый уровень модели обслуживает различные этапы процесса взаимодействия. Посредством деления на уровни сетевая модель OSI упрощает совместную работу оборудования и программного обеспечения. Модель OSI разделяет сетевые функции на семь уровней: прикладной, уровень представления, сессионный, транспортный, сетевой, канальный и физический.

Физический уровень (Physical layer) определяет способ физического соединения компьютеров в сети.

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

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

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

Сессионный (или сеансовый) уровень (Session layer) позволяет двум программам поддерживать продолжительное взаимодействие по сети, называемое сессией (session) или сеансом.

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

Прикладной уровень (Application layer) предоставляет высокоуровневые функции сетевого взаимодействия, такие как передача файлов, отправка сообщений по электронной почте и т.п. (рис. 5.1).

Рис. 5.1. Уровни модели сетевого взаимодействия

 

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

Физический уровень

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

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

Кабель (cable), используемый для построения компьютерных сетей, представляет собой конструкцию, состоящую, из проводников, изолирующих и экранирующих слоев. В современных сетях используются три типа (табл. 5.1) кабеля:

Таблица 5.1