close

Вход

Забыли?

вход по аккаунту

?

Логика в информатике

код для вставкиСкачать
Логика в информатике
Решение уравнений.
Логические основы ПЭВМ.
Логическое уравнение
Логическое уравнение – равенство двух
высказываний, в котором присутствует
логическая переменная, которая
представляет некоторую логическую
функцию.
Пример:
( A B )( X A B ) B X A
Где корень: X = F (A, B)
Решение уравнения
1.
2.
3.
4.
5.
Перейти к префиксной форме записи уравнения,
заменив обозначения отрицаний на ¬
Построить заголовок таблицы истинности
специального вида
Заполнить строки таблицы истинности для всех
сочетаний А и В, подставляя вместо X - 0 или 1.
Сформировать таблицу истинности для X = F (А,B)
По таблице истинности определить вид функции X,
при необходимости воспользовавшись методами
построения СКНФ и СДНФ, которые будут
рассмотрены ниже.
Переход к префиксной форме
Обычная форма:
( A B )( X A B ) B X A
Префиксная форма:
(( A B )( X A B )) ( B ( X A ))
Построение таблицы истинности
специального вида
¬ ((А + B)
· (X A · B)) = ¬ (B + ¬ (X A))
1
0 0
0 0
0
0 0 0
0
1 1 0 0 0
0
1
0
1
0 0
0 0
1
1 0 0
0
0 0 0 1 1
1
0
0
1
0 1
1 0
0
0 0 0
1
0 0 1 1 0
0
1
0
0
0 1
1 1
1
1 0 0
1
1 0 1 1 1
1
0
0
1
1 1
0 0
0
0 1 0
0
1 1 0 0 0
0
1
1
0
1 1
0 1
1
1 1 0
0
0 1 0 0 0
1
1
1
0
1 1
1 1
0
1 1 1
1
1 0 1 1 0
0
1
1
1
1 1
1 0
1
0 1 1
1
0 0 1 1 0
1
1
1
Таблица истинности X=F(A, B)
Соответствует
отрицанию импликации
ВвА
A
B
X
0
0
0
0
1
1
ОТВЕТ:
1
0
0
Х В А
1
1
0
Комбинационные схемы
логических устройств
Базисные элементы (ГОСТ 2.743-91):
А
А
&
1
В
А
В
Дизъюнкция
В
А
M2
В
XOR
Конъюнкция
Эквивалентность
Комбинационные схемы
логических устройств
Базисные элементы (ГОСТ 2.743-91):
А
А
&
1
В
А
В
Импликация
В
А
1
Элемент Вебба
В
Коимпликация
&
Элемент Шеффера
Расшифровка элемента
Коимпликация
Вход 1
Действие
А
&
Выход
Вход 2
В
Отрицание
А·В
Пример схемы
A
1
4
1
2
1
7
&
3
&
5
M2
B
8
6
1
F
&
Решение схем
1 Вариант – преобразование схемы в
сложное логическое выражение и затем
– упрощение его по законам логики.
2 Вариант – построение таблицы
истинности а затем, при необходимости,
построение через СКНФ или СДНФ (см.
ниже).
Рассмотрим второй вариант, как более
простой и понятный.
Построение таблицы истинности
·
·
+
·
+
+
AB
B·A
B
A
A B
A+B
0 0
1 1 1 0 0 0 0 1 0 0 1 0
0 1
1 1 0 0 1 0 1 0 0 0 1 0
1 0
0 0 1 1 1 0 1 0 1 0 1 1
1 1
0 1 0 0 0 0 0 1 0 0 1 0
Таблица истинности F(A, B)
Соответствует
отрицанию импликации
ВвА
A
B
X
0
0
0
0
1
0
ОТВЕТ:
1
0
1
Õ À Â
1
1
0
СДНФ и СКНФ (определения)
Элементарной конъюнкцией называется конъюнкция нескольких
переменных, взятых с отрицанием или без отрицания, причем среди
переменных могут быть одинаковые
X Y X Z
Элементарной дизъюнкцией называется дизъюнкция нескольких
переменных, взятых с отрицанием или без отрицания, причем среди
переменных могут быть одинаковые
X Y X Z
Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной
нормальной формой (ДНФ)
X Y X Z
Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной
нормальной формой (ДНФ)
(X Y )(X Z )
СДНФ и СКНФ (определения)
Совершенной дизъюнктивной нормальной формой (СДНФ),
называется ДНФ, в которой нет одинаковых элементарных конъюнкций и
все конъюнкции состоят из одного и того же набора переменных, в
который каждая переменная входит только один раз (возможно с
отрицанием).
X Y Z X Y Z X Y Z
Совершенной конъюнктивной нормальной формой (СКНФ),
называется КНФ, в которой нет одинаковых элементарных дизъюнкций и
все дизъюнкции состоят из одного и того же набора переменных, в
который каждая переменная входит только один раз (возможно с
отрицанием).
(X Y Z )(X Y Z )(X Y Z )
Алгоритм получения СДНФ
по таблице истинности
1. Отметить строки таблицы истинности в
последнем столбце которых стоят 1.
2. Выписать для каждой отмеченной строки
конъюнкцию всех переменных следующим
образом: если значение переменной в
данной строке равно 1, то в конъюнкцию
включать саму эту переменную, если
равно 0, то ее отрицание.
3. Все полученные конъюнкции связать в
дизъюнкцию.
Пример построения СДНФ
X
0
0
Y
0
1
F(X,Y)
0
1
1. Отметить единицы
2. Конъюнкции:
X·Y
X·Y
1
0
1
1
1
0
3. Дизъюнкция:
X·Y+X·Y
Алгоритм получения СКНФ
по таблице истинности
1. Отметить строки таблицы истинности в
последнем столбце которых стоят 0.
2. Выписать для каждой отмеченной строки
дизъюнкцию всех переменных следующим
образом: если значение переменной в
данной строке равно 0, то в конъюнкцию
включать саму эту переменную, если
равно 1, то ее отрицание.
3. Все полученные дизъюнкции связать в
конъюнкцию.
Пример построения СKНФ
X
0
0
Y
0
1
F(X,Y)
0
1
1. Отметить нули
2. Дизъюнкции:
X+Y
X+Y
1
0
1
1
1
0
3. Конъюнкция:
(X + Y) · (X + Y)
Документ
Категория
Презентации по информатике
Просмотров
140
Размер файла
230 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа