В ы с ш е е п р о ф е с с и о н а л ь н о е о б р а з о в а н и е информатика и программироВание осноВы информатики
жүктеу/скачать 4,7 Mb. Pdf көрінісі
|
1 Основы информатики
| 6.2. логические операции
Основные логические операции над высказываниями, используе- мыми в ЭВМ, включают в себя отрицание, конъюнкцию, дизъюнк- ции, стрелку Пирса и штрих Шеффера. Рассмотрим эти логические операции. 1. Отрицание x – (обозначается также ¬X, ∼X ). Отрицание x – (NOT, читается «не X») — это высказывание, которое истинно, если X ложно, и ложно, если X истинно. 2. Конъюнкция XY (X & Y, X ∧ Y ). Конъюнкция XY (AND, логическое умножение, «X и Y») — это высказывание, которое истинно только в том случае, если X истинно и Y истинно. 3. Дизъюнкция X + Y (X ∨ Y ). Дизъюнкция X + Y (OR, логическая сумма, «X или Y или оба») — это высказывание, которое ложно только в том случае, если X ложно и Y ложно. 4. Стрелка Пирса X ↓ Y. Стрелка Пирса X ↓ Y (NOR (NOT OR), ИЛИ—НЕ) — это выска- зывание, которое истинно только в том случае, если X ложно и Y ложно. 5. Штрих Шеффера X | Y. Штрих Шеффера X | Y (NAND (NOT AND), И — НЕ) — это вы- сказывание, которое ложно только в том случае, если X истинно и Y истинно. Определить значения логических операций при различных соче- таниях аргументов можно из таблицы истинности (табл. 6.1) Чтобы определить значение операции 0 + 1 в таблице истинности, необходимо на пересечении столбца X + Y (определяет операцию) и 50 строки, где X = 0 и Y = 1 (так, первый аргумент равен 0, а второй — 1), найти значение 1, которое и будет являться значением операции 0 + 1. В алгебре высказываний существуют две нормальные формы: конъюнктивная нормальная форма (КНФ) и дизъюнктивная нор- мальная форма (ДНФ). КНФ — это конъюнкция конечного числа дизъюнкций нескольких переменных или их отрицаний (произведение сумм). Например, формула X(Y + Z ) находится в КНФ. ДНФ — это дизъюнкция конечного числа конъюнкций нескольких переменных или их отрицаний (сумма произведений). Например, формула X + YZ находится в ДНФ. Логические операции обладают свойствами, сформулированными в виде равносильных формул. Снятие двойного отрицания отрицание отрицания (Закон «ис- ключения третьего»): X X = . (6.1) Коммутативность • : XY = YX; (6.2) X + Y = Y + X. (6.3) Ассоциативность • : ( XY )Z = X(YZ ); (6.4) ( X + Y ) + Z = X + (Y + Z ). (6.5) Дистрибутивность • : X(Y + Z ) = XY + XZ. (6.6) X + YZ = (X + Y )(X + Z ). (6.7) Т а б л и ц а 6.1. жүктеу/скачать 4,7 Mb. Достарыңызбен бөлісу:
|