Эквиваленция через конъюнкцию и дизъюнкцию

Эквиваленция через конъюнкцию и дизъюнкцию

1) Логическое умножение или конъюнкция:

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

Обозначение: F = A & B.

Таблица истинности для конъюнкции

2) Логическое сложение или дизъюнкция:

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

Обозначение: F = A + B.

Таблица истинности для дизъюнкции

3) Логическое отрицание или инверсия:

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

Таблица истинности для инверсии

4) Логическое следование или импликация:

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

Таблица истинности для импликации

5) Логическая равнозначность или эквивалентность:

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

Таблица истинности для эквивалентности

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

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

11. Предикаты. Операнды. Законы логического вывода.

12. История развития эвм. Поколения вычислительных средств.

13. Понятие и основные виды архитектуры эвм.

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

К архитектуре относятся следующие принципы построения ЭВМ:

структура памяти ЭВМ;

способы доступа к памяти и внешним устройствам;

возможность изменения конфигурации;

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

С точки зрения пользователя общность архитектуры разных компьютеров обеспечивает их совместимость, то есть способность различных объектов (устройств и программ) к взаимодействию. Важнейшую роль в развитии и распространении IBM PC-совместимых компьютеров (клонов) сыграл заложенный фирмой IBM принцип открытой архитектуры, который означает применение при сборке компьютера готовых блоков и устройств (модулей), а также стандартизацию способов их соединения. Любой узел может быть заменен другим и, кроме того, к компьютеру могут быть дополнительно подсоединены другие узлы. Реализация открытости архитектуры была обеспечена благодаря использованию общей шины (магистрали) – принципиально нового устройства связи между отдельными узлами ЭВМ. Принцип построения ЭВМ, в соответствии с которым обмен информацией между устройствами организуется с помощью магистрали, получил название магистрально-модульного принципа. Таким образом, модульная организация компьютера опирается на магистральный (шинный) принцип обмена информацией между модулями.

Один из признаков, по которым классифицируют архитектуры компьютеров, – это разрядность интерфейсов и машинного слова. Разрядности компьютеров могут быть равными 8, 16, 32, 64 двоичных разрядов. Некоторые ЭВМ имеют другие разрядности.

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

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

однопроцессорности с несколькими исполнительными устройствами;

конвейеризации обработки данных.

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

SISD (Single Instruction stream over a Single Data stream) – вычислительная система с одним потоком команд и данных. SISD относят к типу однопроцессорных ЭВМ. Архитектура вычислительной системы с одним процессором является фон-неймановской.

Читайте также:  Прекращена работа программы radeon settings host application

SIMD (Single Instruction Multiple Data) – многопроцессорная вычислительная система с общим потоком команд (одиночный поток команд) и множественным потоком данных. Архитектура SIMD характеризуется тем, что все процессоры выполняют одну и ту же команду, но каждый над своими данными из своей локальной памяти. Такую архитектуру часто называют векторной.

MISD (Multiple Instruction Single Data) – многопроцессорная вычислительная система со множественным потоком команд и одиночным потоком данных (конвейерная ЭВМ). Конвейерная архитектура – это принцип построения компьютера, состоящий в параллельном выполнении команд множеством процессоров над одним потоком данных. Каждый процессор цепочки использует в качестве входных данных выходные данные предыдущего процессора.

MIMD (Multiple Instruction Multiple Data) – многопроцессорная вычислительная система со множественным потоком команд и данных. Каждый процессор здесь функционирует под управлением собственного потока команд, то есть компьютер может параллельно выполнять совершенно разные программы. Современные суперкомпьютеры, как правило, строятся по данной архитектуре.

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

Пример_14: Дана логическая формула . Построить таблицу истинности для данной формулы.

1. Расставляем приоритеты выполнения операций:

1) – операция отрицания высказывания В. Результат выполнения операции присваиваем переменной .

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

3) – операция логического следования (импликация) высказываний и . Результат выполнения операций присваиваем переменной .

2. Строим таблицу, состоящую из пяти столбцов:

Исходные данные
A B

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

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

Исходные данные 1 2 3
A B

Примечание: истина обозначается – 1, а ложь – 0.

4. Заполняем значениями столбец с именем 1. Для этого по таблице истинности для логической операции инверсия (см. таблицу 2) определяем значение операции инверсия Х=0 (при начальном значении В=1).

Исходные данные 1 2 3
A B

5. Заполняем значениями столбец с именем 2. Для этого по таблице истинности основных логических операций (см. таблицу 3) определяем значение операции конъюнкции Y=0 (при А=1 и Х=0) и т.д.

Исходные данные 1 2 3
A B

6. Заполняем значениями столбец с именем 3. Для этого по таблице истинности основных логических операций определяем значение операции логическое следование F=1 (при Y =0 и А=1) и т.д.

Исходные данные 1 2 3
A B

Пример_15: Дана логическая формула . Построить таблицу истинности для данной формулы.

1. Расставляем приоритеты выполнения операций:

1) – операция отрицания высказывания В. Результат выполнения операции присваиваем переменной .

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

3) – операция логического следования (импликация) высказываний и . Результат выполнения операций присваиваем переменной .

2. Строим таблицу, состоящую из пяти столбцов:

Исходные данные
X Y Z

В Исходные данные таблицы записываем имена высказываний X, Y и Z. В остальные четыре столбца записываем имена переменных, которым присваиваем результаты логических операций.

3. Исходные данные таблицы заполняем возможными комбинациями значений высказываний X, Y и Z (первый вариант – когда все высказывания истинны; второй вариант – когда два высказывания истинны, а третье ложно; третий вариант – когда одно из высказываний истинно, а другие ложны; четвертый вариант – когда все три высказывания ложны).

Исходные данные
X Y Z

Примечание: истина обозначается – 1, а ложь – 0.

4. Заполняем значениями столбец с именем 1. Для этого по таблице истинности для логической операции антиконъюнкция (см. таблицу 2) определяем значения.

Исходные данные
X Y Z

5. Заполняем значениями столбец с именем 2. Для этого по таблице истинности основных логических операций (см. таблицу 3) определяем значение операции конъюнкции Y=0 (при А=1 и Х=0) и т.д.

Исходные данные
X Y Z

6. Заполняем значениями столбец с именем 3. Для этого по таблице истинности основных логических операций определяем значение операции логическое следование F=1 (при Y =0 и А=1) и т.д.

Исходные данные
X Y Z

Логические основы ЭВМ

Для описания того, как функционируют аппаратные средства компьютера очень удобен математический аппарат алгебры логики, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры «1» и «0».

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

Читайте также:  Видео обзор лексус nx 200

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

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

Логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-НЕ». С помощью этих схем можно реализовать любую логическую формулу, описывающую работу устройств компьютера.

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

Схема «И» реализует конъюнкцию двух или более логических значений. Условное обозначение структурной схемы «И» представлена на рис. 2.1.2.

Рис. 2.1.2. Схема «И»

На выходе схемы «И» значение «1» будет тогда и только тогда, когда на всех входах будут «1». Когда хотя бы на одном входе будет «0», на выходе также будет «0».

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

Схема «ИЛИ» реализует дизъюнкцию двух логических значений. Условное обозначение схемы «ИЛИ» представлено на рис. 2.1.3.

Рис. 2.1.3. Схема «ИЛИ»

На выходе схемы «ИЛИ» значение «0» будет тогда и только тогда, когда на всех входах будут «0». Когда хотя бы на одном входе будет «1», на выходе также будет «1».

Операция дизъюнкции на функциональных схемах обозначается знаком «1».

Схема «НЕ» (инвертор) реализует операцию отрицания. Условное обозначение схемы НЕ представлено на рис. 2.1.4.

Рис. 2.1.4. Схема «НЕ»

Если на входе схемы – «0», то на выходе будет «1». Когда на входе – «1», на выходе будет «0».

Схема «И-НЕ» состоит из элемента «И» и инвертора и осуществляет отрицание результата схемы «И». Условное обозначение схемы «И-НЕ» представлено на рисунке 2.1.5.

Рис. 2.1.5. Схема «И-НЕ»

На выходе схемы «И-НЕ» значение «0» будет тогда и только тогда, когда на всех входах будут «1».

Схема «ИЛИ-НЕ» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата схемы «ИЛИ». Условное обозначение схемы «ИЛИ-НЕ» представлено на рис. 2.1.6.

Рис. 2.1.6. Схема «ИЛИ-НЕ»

На выходе схемы «ИЛИ-НЕ» значение «1» будет тогда и только тогда, когда на всех входах будут «0».

Вопросы для самоконтроля

1. Что изучает дисциплина информатика?

2. Дайте определение понятию «информация».

3. Формы представления информации.

4. Перечислите свойства информации.

5. Какова минимальная единица измерения информации?

6. Какова основная единица измерения информации?

7. Как задаются производные единицы измерения информации?

8. Дайте определение понятию «количество информации».

9. Как связаны между собой понятия «энтропия» и «информация»?

10. Что измеряет синтаксическая мера информации?

11. Что измеряет семантическая мера информации?

12. Что измеряет прагматическая мера информации?

13. Дайте определение понятию «система счисления».

14. Чем отличается позиционная система счисления от непозиционной?

15. Приведите примеры позиционной и непозиционной систем счисления.

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

17. Как представляются данные в компьютере?

18. Для чего используется кодовая таблица?

19. Как кодируются символы в памяти компьютера?

20. Что собой представляет таблица ASCII кодов?

21. Как определить числовой код символа?

22. Представление целых положительных и отрицательных чисел в прямом, обратном и дополнительном кодах.

23. Правила сложения и вычитания положительных и отрицательных чисел в обратном коде.

24. Правила сложения и вычитания положительных и отрицательных чисел в дополнительном коде.

25. Что изучает алгебра логики?

26. Что понимается под высказыванием?

27. Перечислите основные логические операции?

28. Для каждой логической операции назовите соответствующие логические связки.

29. Для чего используется таблица истинности?

30. Для высказываний А=«На улице светит солнце» и В=«Идет дождь» примените операцию конъюнкции. Какое новое высказывание получилось?

31. Для высказываний А=«У меня в зачетке стоят одни пятерки» и В=«Я добросовестно выполняю задания» примените операцию эквиваленции. Какое новое высказывание получилось?

32. Как изображается логическая схема «И-НЕ»?

33. Как изображается логическая схема «ИЛИ»?

34. Как изображается логическая схема «НЕ»?

35. Через какие логические операции можно реализовать импликацию?

36. Через какие логические операции можно реализовать эквиваленцию?

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

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

Читайте также:  Как понять что в вотсапе тебя заблокировали

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

Операция конъюнкция выражается с помощью операций дизъюнкции.

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

Операция «р влечёт q» и называется импликацией (с предварительным членом р и с последующим членом q).

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

Если высказывание «горит лампочка» правильно, то правильностью высказывания «лифт работает» однозначно решается правильность вышеприведенного предложения. Но если высказывание «горит лампочка» ложно, то ничего нельзя сказать о правильности вышеприведенного предложения. Можно сказать : надо подождать, пока лампочка загорится Приведем пример, в котором не будет даже возможности «подождать»:

Если 2 * 2 = 5, то Дунай является европейской рекой. Если принять то, что соединение типа «если . . .то» соответствует операции импликации, при соблюдении последнего тождества высказывание «если А, то В» выражалось бы с помощью операций конъюнкции и отрицания в следующем виде : «неправильно, что : А и не В» (здесь присутствует выражение «не В» вместо выражения «неправильно, что В»; таким образом, ясно, что выражение «неправильно, что», расположенное в начале высказывания, относится не только к Л, но и к выражению «А и не В»). В соответствии с этим приведенные выше два предложения в примере могут быть переформулированы следующим образом:

  • а) Неправильно, что горит лампочка и лифт не работает.
  • б) Неправильно, что 2 * 2 = 5 и Дунай не является европейской рекой. Если выражение «горит лампочка» ложно, то ложно и выражение «лампочка горит и лифт не работает», а отрицание его — по а) — является правильным. Выражение. «2 * 2 = 5» ложно, ложно также и выражение «Дунай не является европейской рекой»; их конъюнкция — также ложна, а отрицание этой конъюнкции — по б) — является правильным. Здесь нет противоречия по сравнению с обычным пониманием вещей, так как обычно не обращают внимание на правильность сложного предложения типа «если . . . то» в том случае, когда первый член соединения является ложным.

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

Представленное в области логических значений понятие импликации типа р влечёт q соответствует понятию вышеприведенной операции высказывания.

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

Упоминаются еще некоторые грамматические синонимы операции «А влечёт В»: «В, если только Л», «Только тогда А, если В», «Достаточным условием В является А», «Необходимым условием А является В», «В если не А».

И конъюнкция и дизъюнкция выражаются с помощью операций импликации и отрицания.

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

Последний вид выражения операции эквивалентности.

Так как высказывание p эквивалентно q = n тогда и только тогда, когда p = q, то данная логическая операция соответствует образованию сложного предложения вида «А тогда и только тогда, когда В». Понимание и логическое значение предложения такого характера, образованного из двух любых высказываний, иногда затруднительно для восприятия человека, как и понимание предложения вида «если . . . то». Например, «2

Ссылка на основную публикацию
Шаблоны букв английского алфавита для вырезания
Трафареты и шаблоны букв английского алфавита для вырезания из бумаги, это разнообразные шрифты разного стиля и тематики. Трафареты помогут вам...
Что значит спящий режим компьютера
В операционной системе Windows есть несколько режимов выключения компьютера – это обыкновенный режим, (который полностью выключает PC), режим гибернации и...
Что значит сторнировать документ
Сто́рно (итал. storno — перевод на другой счёт, отвод; от stornare — поворачивать обратно) — в общем смысле возврат к...
Шаблоны для брошюры в ворде
Автор: admin Дата записи Быстрей всего набросать буклет, если под рукой окажется готовый шаблон. Проще всего создать буклет в программе...
Adblock detector