Уравнения на логику. Решение логических уравнений и систем логических уравнений. Логические элементы ЭВМ. Построение функциональных схем

Лекция на тему

Уравнения на логику. Решение логических уравнений и систем логических уравнений. Логические элементы ЭВМ. Построение функциональных схем

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

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

  2. Построение логических схем.

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

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

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

Преобразование сигнала логическим элементом задается таблицей состояния, которая фактически является таблицей истинности, соответствующей логической функции.

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

ИЛИ ДРУГОЙ ВИД ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ

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

Если элемент имеет входное напряжение от 0 до 0,4В, то оно рассматривается как логический 0, если напряжение в пределах от 0,7 до 1,5В, то оно рассматривается как 1. Примерно такие же характеристики имеет выходное напряжение.

  1. Построить схемы

Пример 1. Составить схему

Результат:

Пример 2. Составить схему

Результат:

Пример 3. Составить схему

Результат:

Пример 4. Составить схему

Результат:

Пример 5. Составить схему

Результат:

Пример 6. Составить схему

Результат:

Пример 7. Составить схему

Результат:

II. Выполним задачу обратную данной. Составим логическое выражение по заданной логической схеме:

Данное логическое выражение можно упростить.

Операция И – логическое умножение, ИЛИ – сложение. Запишем выражение, заменяя знаки & и U на * и + соответственно.

Упростим , затем запишем

)

  и тогда логическая схема примет вид:

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

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

По заданной логической функции построить логическую схему.

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

Пример 2. Выписать из логической схемы соответствующую ей логическую формулу:

Решение:

  1. Построение логических схем.

Вариант 1.

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

Решение:

2. Выписать из логической схемы соответствующую ей логическую формулу:

Решение:

Вариант 2.

1. По заданной логической функции построить логическую схему и таблицу истинности.
Решение:

2. Выписать из логической схемы соответствующую ей логическую формулу:

Решение:

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

Контрольные вопросы:

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

  2. Что такое логическое умножение?

  3. Что такое логическое сложение?

  4. Что такое инверсия?

  5. Что такое таблица истинности?

  6. Что такое сумматор?

  7. Что такое полусумматор?

Литература, ЭОР:

  1. Информатика и информационные технологии. Учебник для 10-11 классов,Н. Д. Угринович – 2007г.;

2. Практикум по информатике и информационным технологиям. Учебное пособие для общеобразовательных учреждений, Н. Д. Угринович, Л. Л. Босова, Н. И. Михайлова – 2007г.

Источник: https://infourok.ru/lekciya-na-temu-postroenie-logicheskih-shem-s-pomoschyu-bazovih-logicheskih-elementov-po-discipline-osnovi-matematicheskoy-logik-1864411.html

���������� �������� �, ���, ��, �-��, ���-�� � �� ������� ����������

Уравнения на логику. Решение логических уравнений и систем логических уравнений. Логические элементы ЭВМ. Построение функциональных схем

������������� �����, ��������������� ��� ���������� �����-���� ���������� �������� � �������� �������, ���������� ���������� ���������. ������� ������ �������������� ����� � ���� ���������� ��������� �������, � ��������� ���������� �������� �� ������ � ����� ���������� � ���� ���������� ������������� ������.

�������� � ������ ������ �������� � �������� ������� ��������� � �� ���� ����������� �������� ��������� ������� � ����� ���������� �������� ��� ������� ������, ������� � ������ �� ���� �������� �������. ���, ���������� �������� ������ � ��� ���������� ������� 1 � ���������� �������� �������� ��������, � ���������� ������� ������ 0 � �������� ������. 1 � ������, 0 � ����.

���������� ������� � �������, �������������� ������������ ���������� ����������� ����� �������� � ��������� ���������.

���������� �������� ������ ������������ ��� ���������� ���������� ���� �������������� �����, ���������� ���� ��������������� �������� � ����������.

��� ���� ����� ���������� ���������, ���������� �� �� ���������� �������, ���������� ���������� �������� ������� � �������� ��������.

���������� �������� ����� ���� ��� ��������� ������ � ���� ��� ��� (������ ��������� ���� �����) ������.

�������� ������ � �������� �������� �������� ���������� ��������� ������������ ���������� ��������, ������� ��������� �������, � ���������� ������ � �������� ������� ��������, �������� ���� ����������� ����������.

���������� ������������ ���������� �������, �� ������� ����� ��������� ����� ������� ���������� �������.

� ����������� �� ���������� ����� ��������, �� �� ������������� ����������, ���������� ������ (������� � ������ ������ ����������) ����� � ������ ����� ���������� �������� ��� �������� � ������� (��������� � �������) ���������.

����������� ���������� �������� ����������� � ���� ����������� ������������ � ������������ ���������. ���������� ��������, ����� ��� ����������, ����������, ��������� � �������� �� ������ (�, ���, ��, ����������� ���) � �������� ��������� ����������, ������������ �� ���������� ��������� �������� �����. ����� ���������� ������ �� ���� ����� ���������� ��������� ����� �����������.

���������� ������� �Ȼ – ����������, ���������� ���������, AND

�Ȼ – ���������� �������, ����������� ��� �������� ������� �������� ���������� ��� ����������� ���������. ������ ������� ����� ����� �� 2 �� 8 (�������� �������������� � ������������ �������� �Ȼ � 2, 3, 4 � 8 �������) ������ � ���� �����.

�������� ����������� ���������� ��������� �Ȼ � ������ ����������� ������ ��������� �� �������. � ������ ���������� ������� �Ȼ � ��� ��� ���� ������ ������ ������������ ��� �2Ȼ, �4Ȼ � �. �. – ������� �Ȼ � ����� �������, � �������� ������� � �. �.

������� ���������� ��� �������� 2� ����������, ��� �� ������ �������� ����� ���������� ������� ���� � ��� ������, ���� ���������� ������� ����� ������������ �� ������ ����� � �� ������ �����. � ��������� ���� ��������� ������� �� ������ ����� ����.

�� �������� ������ ������ �������� �Ȼ ����� ������ ����� �� ����� � ����������� �� ������. �� ������������� ������ � ������������� � �������� �&�.

���������� ������� ���Ȼ – ����������, ���������� ��������, OR

���Ȼ – ���������� �������, ����������� ��� �������� ������� �������� ���������� ��� ����������� ��������. �� ��� �� ��� � ������� �Ȼ ����������� � �����, �����, �������� � �. �. ������� � � ����� �������. �������� ����������� ���������� ��������� ���Ȼ � ��������� ����������� ������ �������� �� �������. ������������ ������ �������� ���: 2���, 3���, 4��� � �. �.

������� ���������� ��� �������� �2��Ȼ ����������, ��� ��� ��������� �� ������ ���������� �������, ���������� ����� ���������� ������� ���� �� ������ ����� ��� �� ������ �����. ���� ���������� ������� ����� ����� �� ���� ������, �� ������ ����� ����� �������.

�� �������� ������ ������ �������� ���Ȼ ����� ����������� �� ����� � ����������� � ����������� �� ������. �� ������������� ������ � ������������� � �������� �1�.

���������� ������� ��Ż – ���������, ��������, NOT

��Ż – ���������� �������, ����������� ��� �������� ������� �������� ����������� ���������. ������ �������, ������� ���� ����� � ������ ���� ����, �������� ��� ����������, ��������� �� �� ����� ���� ����������� (��������) ������� ������. �� ������� ��������� �������� ����������� ����������� �������� ��Ż.

������� ���������� ��� ��������� ����������, ��� ������� ��������� �� ����� ��� ������ ��������� �� ������ � ��������.

�� �������� ������ ������ �������� ��Ż ����� ����� ������������ � ��������� �� ������. �� ������������� ������ � ������������� � �������� �1�, � ������� �� ������.

���������� ������� ��-�Ż – ���������� (���������� ���������) � ����������, NAND

��-�Ż – ���������� �������, ����������� ��� �������� ������� �������� ����������� ��������, � ����� �������� ����������� ���������, ��������� �������� �� �����. ������� �������, ��� � �������� ������� �Ȼ, ����������� ��������� ��Ż. �� ������� ��������� �������� ����������� ����������� �������� �2�-�Ż.

������� ���������� ��� �������� ��-�Ż �������������� ������� ��� �������� �Ȼ. ������ ���� ����� � ������� � ��� ������� � ����. ������� ��-�Ż �������� ��� �������� ������� � ����� ���������� ����� ������ �������, ������� ����������� ���������� ���� ���������� �������� � 1913 ����. ������������ ��� �Ȼ, ������ � ��������� �� ������.

���������� ������� ����-�Ż – ���������� (���������� ��������) � ����������, NOR

����-�Ż – ���������� �������, ����������� ��� �������� ������� �������� ����������� ��������, � ����� �������� ����������� ���������, ��������� �������� �� �����. ����� ������, ��� ������� ���Ȼ, ����������� ��������� ��Ż – ����������. �� ������� ��������� �������� ����������� ����������� �������� �2���-�Ż.

������� ���������� ��� �������� ����-�Ż �������������� ������� ��� �������� ���Ȼ. ������� ��������� �� ������ ���������� ���� � ����� ������ – �� ��� ����� �������� ������������ ������ ����������. ������������ ��� ���Ȼ, ������ � ��������� �� ������, ������������ ��������.

���������� ������� ������������ ��Ȼ – �������� �� ������ 2, XOR

������������ ��Ȼ – ���������� �������, ����������� ��� �������� ������� �������� ����������� �������� �� ������ 2, ����� ��� ����� � ���� �����. ����� ������ �������� ��������� � ������ ��������. �� ������� ��������� �������� ����������� ������� ��������.

����������� � �������� ������ � ��� � ���Ȼ � �������������� ��������� �������� �� ������� �����, � ������������� � ��� ���Ȼ, ������ ������ �1� ����� �������� �=1�.

���� ���������� ������� ��� �������� ������������������. ������� ������� ���������� ����� �� ������ ���� �����, ����� ������� �� ����� �� ����� (�� ����� �������, �� ������ ���� ��� �� ����� ����, � �� ������ �������) ���� ���� �� ����� ����� ������������ ��� �������, �� ������ ����� ���� � � ���� ������� �� ���Ȼ. ������ �������� ������ ������ ����������� � ����������.

Источник: http://ElectricalSchool.info/electronica/1918-logicheskie-jelementy-i-ili-ne-i-ne-ili.html

Построение логических схем

Уравнения на логику. Решение логических уравнений и систем логических уравнений. Логические элементы ЭВМ. Построение функциональных схем

Цели урока:

Образовательные:

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

Развивающие:

  • формировать развитие алгоритмического мышления;
  • развить конструкторские умения;
  • продолжать способствовать развитию ИКТ – компетентности;

Воспитательные:

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

Требования к знаниям и умениям:

Учащиеся должны знать:

  • основные базовые элементы логических схем;
  • правила составления логических схем.

Учащиеся должны уметь:

  • составлять логические схемы.

Тип урока: урок закрепления изученного материала

Вид урока: комбинированный

Методы организации учебной деятельности:

  • фронтальная;
  • индивидуальная;

Программно-дидактическое обеспечение:

  • ПК, SMART Board, карточки с индивидуальным домашним заданием.

Урок разработан с помощью программы Macromedia Flash.

Ход урока

I. Постановка целей урока.

Добрый день!

Сегодня мы продолжаем изучение темы “Построение логических схем”.

Приготовьте раздаточный материал “Логические основы ЭВМ. Построение логических схем” Приложение 1

Вопрос учителя. Назовите основные логические элементы. Какой логический элемент соответствует логической операции И, ИЛИ, НЕ?

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

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

Ответ учащихся. На первом входе есть ток (1, истина), на втором есть (1, истина), на выходе ток идет (1, истина).

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

Ответ учащихся. Элемент ИЛИ – дизъюнктор.

Вопрос учителя. Рассмотрим логический элемент НЕ. В каком случае на выходе не будет тока (сигнал равный 0)?

Ответ учащихся. На входе есть ток, сигнал равен 1.

Вопрос учителя. В чем отличие логической схемы от логического элемента?

Ответ учащихся. Логические схемы состоят из логических элементов, осуществляющих логические операции.

Проанализируем схему и определим сигнал на выходе.

II. Закрепление изученного материала.

Почему необходимо уметь строить логические схемы?

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

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

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

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

Вопрос учителя. Каков алгоритм построение логических схем?

Ответ учащихся. Алгоритм построение логических схем:

Определить число логических переменных.

Определить количество базовых логических операций и их порядок.

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

Соединить вентили в порядке выполнения логических операций.

Работа со SMART Board Приложение 2

Проверка домашнего задания Приложение 1. Домашнее задание. Часть 1

Построить логическую схему для логического выражения: .

  1. Две переменные – А и В.
  2. Две логические операции: &,
  3. Строим схему.

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

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

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

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

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

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

Вычислить значение данного выражения для А=1, В=0.

Ответ F=1

III. Пропедевтика (законы логики)

Выполним задачу обратную данной. Составим логическое выражение по заданной логической схеме:

Данное логическое выражение можно упростить.

Операция И – логическое умножение, ИЛИ – сложение. Запишем выражение, заменяя знаки & и U на * и + соответственно.

F= (A*B+B*С) Упростим F= (B*(А+С)), затем запишем и тогда логическая схема примет вид:

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

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

Таким образом, цель нашего следующего урока – изучить законы алгебры логики.

IV. Домашнее задание. Часть 2

V. Практическая работа.

Программа – тренажер “Построение логических схем”

www.Kpolyakov.narod.ru Программа “Logic”,

Спасибо за урок!

14.03.2012

Источник: https://urok.1sept.ru/%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8/613002/

7. Системы логических уравнений – Информатика

Уравнения на логику. Решение логических уравнений и систем логических уравнений. Логические элементы ЭВМ. Построение функциональных схем

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

Задача: Решить систему логических уравнений:

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

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

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

Решение 1: Применяем инверсию к обеим частям первого уравнения:

Представим импликацию через базовые операции «ИЛИ», «НЕ»:

Поскольку левые части уравнений равны 1, можно объединить их с помощью операции “И” в одно уравнение, равносильное исходной системе:

Раскрываем первую скобку по закону де Моргана и преобразовываем полученный результат:

Полученное уравнение, имеет одно решение: A=0, B=0 и C=1.

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

Решение 2: Составим таблицу истинности для системы:

ABC
111011
110011
101011
100011
011111
010110
001101
000100

Полужирным выделена строчка, для которой выполняются условия задачи. Таким образом, A=0, B=0 и C=1.

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

Решение 3: Пусть A = 0, тогда:

Из первого уравнения получаем B=0, а из второго – С=1. Решение системы: A = 0, B = 0 и C = 1.

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

Основной способ нахождения количества решений системы логических уравнений – замена переменных.

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

Задача: Сколько решений имеет уравнение (A→B) + (C→D) = 1? Где A, B, C, D – логические переменные.

Решение: Введем новые переменные: X = A→B и Y = C→D. С учетом новых переменных уравнение запишется в виде: X + Y = 1.

Дизъюнкция верна в трех случаях: (0;1), (1;0) и (1;1), при этом X и Y является импликацией, то есть является истинной в трех случаях и ложной – в одном. Поэтому случай (0;1) будет соответствовать трем возможным сочетаниям параметров. Случай (1;1) – будет соответствовать девяти возможным сочетаниям параметров исходного уравнения. Значит, всего возможных решений данного уравнения 3+9=15.

Следующий способ определения количества решений системы логических уравнений – бинарное дерево. Рассмотрим данный метод на примере.

Задача: Сколько различных решений имеет система логических уравнений:

Приведенная система уравнений равносильна уравнению:

(x1 → x2)*( x2 → x3)*…*( xm-1 → xm) = 1.

Предположим, что x1– истинно, тогда из первого уравнения получаем, что x2 также истинно, из второго – x3=1, и так далее до xm = 1. Значит набор (1; 1; …; 1) из m единиц является решением системы. Пусть теперь x1=0, тогда из первого уравнения имеем x2 =0 или x2 =1.

Когда x2 истинно получаем, что остальные переменные также истинны, то есть набор (0; 1; …; 1) является решением системы. При x2=0 получаем, что x3=0 или x3=, и так далее. Продолжая до последней переменной, получаем, что решениями уравнения являются следующие наборы переменных (m+1 решение, в каждом решении по m значений переменных):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Такой подход хорошо иллюстрируется с помощью построения бинарного дерева. Количество возможных решений – количество различных ветвей построенного дерева. Легко заметить, что оно равно m+1.

ДеревоКоличество решений
x1
x23
x34

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

Перепишем систему уравнений в виде:

И составим таблицу истинности отдельно для одного уравнения:

x1x2(x1 → x2)
001
011
100
111

  Составим таблицу истинности для двух уравнений:

x1x2x3x1 → x2x2 → x3(x1 → x2) * (x2 → x3)
000111
001111
010100
011111
100010
101010
110100
111111

Далее можно увидеть, что одно уравнение истинно в следующих трех случаях: (0; 0), (0; 1), (1; 1). Система двух уравнений истина в четырех случаях (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1).

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

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

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

Источники: http://www.rusnauka.com/20_DNII_2012/Pedagogica/5_114213.doc.htmВспомним пройденное!

Источник: https://www.sites.google.com/a/gkl-kemerovo.ru/informatics/logic/7-sistemy-logiceskih-uravnenij

Задача №23. Решение систем логических уравнений

Уравнения на логику. Решение логических уравнений и систем логических уравнений. Логические элементы ЭВМ. Построение функциональных схем

Автор материалов – Лада Борисовна Есакова.

Решение систем логических уравнений методом замены переменных

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

Пример 1.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1  → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

y1

y2

y3

y4

0

0

0

0

0

0

0

1

0

0

1

1

0

1

1

1

1

1

1

1

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0  достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

y1

y2

y3

y4

Кол-во наборов на x1…x8

0

0

0

0

1*1*1*1 = 1

0

0

0

1

1*1*1*3 = 3

0

0

1

1

1*1*3*3 = 9

0

1

1

1

1*3*3*3 = 27

1

1

1

1

3*3*3*3 = 81

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Ответ: 121

Пример 2.

Сколько существует различных наборов значений логических переменных x1, x2, … x9, y1, y2, … y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x9, y1, y2, … y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

z1z2z3z4z5z6z7z8z9
010101010
101010101

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 – два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 29 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 29 +29 = 1024 наборов.

Ответ:1024

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Пример 3.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

¬x1 ∨ x2 = 1

¬x2 ∨ x3 = 1

¬x9 ∨ x10 = 1,

где x1, x2, … x10 — ло­ги­че­ские пе­ре­мен­ные?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний x1, x2, … x10, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 ( 0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 ( 0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

Ni+1 = Ni + 1. Тогда для десяти переменных получим 11 наборов.

Ответ: 11

Решение систем логических уравнений различного типа

Пример 4.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, …, x4, y1,…, y4, z1,…, z4, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1

(z1 → z2) ∧ (z2→ z3) ∧ (z3 → z4) = 1

x4 ∧ y4 ∧ z4 = 0

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, …, x4, y1, …, y4, z1, …, z4, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

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

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

x1

x2

x3

x4

0

0

0

0

0

0

0

1

0

0

1

1

0

1

1

1

1

1

1

1

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x4 ∧ y4 ∧ z4 = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль : (0, 0), (0,1) , (1,0).

x1

x2

x3

x4

Кол-во наборов

 (y4, z4)

0

0

0

0

5*5 = 25

0

0

0

1

1 + 4 + 4 = 9

0

0

1

1

1 + 4 + 4 = 9

0

1

1

1

1 + 4 + 4 = 9

1

1

1

1

1        + 4 + 4 = 9

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Ответ: 61

Решение систем логических уравнений методом построения рекуррентных формул

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

Пример 5.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

(x7 ∨ y7) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, …, x7, y1, y2, …, y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

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

Обозначим:

число наборов (0,0) на переменных (x1,y1) через A1,

число наборов (0,1) на переменных (x1,y1) через B1,

число наборов (1,0) на переменных (x1,y1) через C1,

число наборов (1,1) на переменных (x1,y1) через D1.

число наборов (0,0) на переменных (x2,y2) через A2,

число наборов (0,1) на переменных (x2,y2) через B2,

число наборов (1,0) на переменных (x2,y2) через C2,

число наборов (1,1) на переменных (x2,y2) через D2.

Из дерева решений видим, что

A1=0, B1=1, C1=1, D1=1.

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A2=B1+C1+D1.

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B2=B1+C1+D1.

Аналогично рассуждая, заметим, что С2=B1+C1+D1. D2= D1.

Таким образом, получаем рекуррентные формулы:

Ai+1 = Bi + Ci + Di

Bi+1 = Bi + Ci + Di

Ci+1 = Bi + Ci + Di

Di+1 = Ai +Bi + Ci + Di

Составим таблицу

НаборыОбозн.Формула

Количество наборов

i=1i=2i=3i=4i=5i=6i=7
(0,0)AiAi+1=Bi+Ci+Di037153163127
(0,1)BiBi+1=Bi+Ci+Di137153163127
(1,0)CiCi+1=Bi+Ci+Di137153163127
(1,1)DiDi+1=Di1111111

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A7.

Тогда общее количество наборов равно B7 + C7 + D7 = 127+127+1 = 255

Ответ: 255

Источник: https://ege-study.ru/ru/ege/materialy/informatika/zadanie-23/

WikiMedForum.Ru
Добавить комментарий