алгебра логики. Алгебра логики Содержание
 Скачать 361.22 Kb.
|
Алгебралогики Содержание
Алгебра – это отрасль математики, посвященная изучению алгебраических операций. Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами. Например, предложение "6 — четное число." следует считать высказыванием, так как оно истинное. Предложение " Москва — столица Франции." тоже высказывание, так как оно ложное. не всякое предложение является логическим высказыванием. Но Существуют разные варианты обозначения истинности и ложности логических переменных:
Условия чтобы предложение являлось высказыванием:
Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие "интересный предмет". Предложения типа "В городе A более миллиона жителей.", "У него голубые глаза." не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь. Такие предложения называются высказывательными формами. Высказывательная форма — это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями. Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание "Площадь поверхности Индийского океана равна 75 млн кв. км." в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике. Задание Какие из предложений являются высказываниями? Определите их истинность.
Не является высказыванием. Высказывание; истина. Высказывание; ложь. Высказывание; ложь. Не является высказыванием. Не является высказыванием. Не является высказыванием. Не является высказыванием. Высказывание; истина. Высказывание; истина. Высказывание; ложь. Высказывание Простое Сложное (составное) это набор простых высказываний (два и более простых высказываний) связанных логическими операциями («И», «ИЛИ», «НЕ», «ЕСЛИ…, ТО», «ТОГДА И ТОЛЬКО ТОГДА»). это повествовательное предложение, относительно которого имеет смысл говорить, истинно оно или ложно. Примеры Примеры:
У кошки 1 хвост. У кошки 4 лапы И 1 хвост. Часть туристов любят молоко. Часть туристов любят чай ИЛИ молоко. A B A ^ B A B A v B Простое высказывание Сложное (составное) высказывание Основные логические связки
КОНЪЮНКЦИЯКОНЪЮНКЦИЯСоответствует союзу И;Обозначение &;В языках программирования and;Название: Логическое умножение.A B F (A^B) &
Вывод: результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны. Операция конъюнкции на структурных схемах обозначается знаком "&" (читается как "амперсэнд"), являющимся сокращенной записью английского слова and. Таблица истинности Схема Таблица истинности для И
Вывод:результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны.ДИЗЪЮНКЦИЯ Соответствует союзу ИЛИ; Обозначение V; В языках программирования or; Название: Логическое сложение. A B F (AvB) 1 Знак "1" на схеме — от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Таблица истинности
Вывод: результат будет ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным в остальных случаях. Таблица истинности для ИЛИ
Вывод: ИНВЕРСИЯ Соответствует союзу НЕ; Обозначение Ā; В языках программирования not; Название: Отрицание. A Ā Вывод: результат будет ложным, если исходное выражение истинно, и наоборот. Таблица истинности для НЕ
Вывод: Таблица истинности для эквивалентности
Вывод: результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны. Вывод: ТриггерТриггер — это электронная схема, широко применяемая в регистрах компьютера для надёжного запоминания одного разряда двоичного кода. Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое — двоичному нулю.Самый распространённый тип триггера — так называемый RS-триггер (S и R, соответственно, от английских set — установка, и reset — сброс).Условное обозначение триггера:
СумматорСумматор — это электронная логическая схема, выполняющая суммирование двоичных чисел. Условное обозначение одноразрядного сумматора:
1. цифра ai первого слагаемого; 2. цифра bi второго слагаемого; 3. перенос pi–1 из младшего разряда. 1. цифра ci для суммы; 2. перенос pi из данного разряда в старший. Таким образом, одноразрядный двоичный сумматор есть устройство с тремя входами и двумя выходами, работа которого может быть описана следующей таблицей истинности. Таблица истинности:
Определение логической формулы:
Порядок выполнения логических операций1. отрицание (“¬”)↔ 2. конъюнкция (“^”) 3. дизъюнкция (“v”) 4. импликация (“”) 5. эквивалентность (“ ”) Для изменения указанного порядка выполнения операций используются скобки. Тавтология
Тождественная истинаПри всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.Тождественная ложьВ качестве другого примера рассмотрим формулу А • , которой соответствует, например, высказывание “Катя самая высокая девочка в классе, и в классе есть девочки выше Кати”. Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно.Такие формулы называются тождественно ложными формулами или противоречиями.Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.Тождественная ложьПри всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.Выполнимая формулаФормула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.позволяют производить тождественные преобразования логических выражений:Таблица истинностиТаблица истинности - таблица, определяющая значение сложного высказывания при всех возможных значениях простых высказываний.
(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). ПримерКак составлять таблицу истинности 1) Определить количество строк: количество строк = 2n + строка для заголовка, где n - количество простых высказываний. 2) Определить количество столбцов: количество столбцов = количество переменных + количество логических операций; • определить количество переменных (простых выражений); • определить количество логических операций и последовательность их выполнения. 3) Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций. Пример1) Определить количество строк: на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 23+1 = 9. 2) Определить количество столбцов: • простые выражения (переменные): А, В, С; • промежуточные результаты (логические операции): ¬ А - инверсия; B V C - операция дизъюнкции; а также искомое окончательное значение арифметического выражения: F=¬A&(B˅C). 3) Заполнить столбцы с учетом таблиц истинности логических операций. Пример: Составить таблицу истинности логического выражения: F = ¬ А & (B V C)
|