Закон идемпотентности доказательство

  • ПРЕДИСЛОВИЕ
    Глава первая. ЭЛЕМЕНТЫ ЛОГИКИ
  • § 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
  • Формулы логики высказываний.
  • Законы логики.
  • Упражнения
  • § 2. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ
  • Схемы доказательств.
  • § 3. ПРЕДИКАТЫ
  • Предикаты.
  • Операции над предикатами.
  • Упражнения
  • § 4. КВАНТОРЫ
  • Запись высказываний на языке логики предикатов.
  • Упражнения
  • § 5. ПРЕДИКАТНЫЕ ФОРМУЛЫ. ЗАКОНЫ ЛОГИКИ
  • Предикатные формулы.
  • Законы логики предикатов.
  • Упражнения
    Глава вторая. МНОЖЕСТВА И ОТНОШЕНИЯ
  • § 1. МНОЖЕСТВА
  • Подмножества.
  • Пустое множество.
  • Операции над множествами.
  • Основные свойства операций над множествами.
  • Универсальное множество. Дополнение множества.
  • Диаграммы Эйлера — Венна.
  • Упражнения
  • § 2. БИНАРНЫЕ ОТНОШЕНИЯ
  • Упражнения
  • § 3. ФУНКЦИИ
  • Композиция функций.
  • Инъективные функции.
  • Обратимые функции.
  • Ограничение функции.
  • Упражнения
  • § 4. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ
  • Отношение эквивалентности.
  • Фактор-множество.
  • Отношение равнообразности отображения.
  • Упражнения
  • § 5. ОТНОШЕНИЯ ПОРЯДКА
  • Упорядоченное множество.
  • Упражнения
    Глава третья. АЛГЕБРЫ И АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
  • § 1. БИНАРНЫЕ ОПЕРАЦИИ
  • Виды бинарных операций.
  • Нейтральные элементы.
  • Симметричные элементы.
  • Подмножества, замкнутые относительно операций.
  • Аддитивная и мультипликативная формы записи.
  • Конгруэнция.
  • Упражнения.
  • § 2. АЛГЕБРЫ
  • Гомоморфизмы алгебр.
  • Подалгебры.
  • Фактор-алгебра.
  • Упражнения
  • § 3. ГРУППЫ
  • Примеры групп.
  • Простейшие свойства группы.
  • Гомоморфизмы групп.
  • Подгруппы.
  • Упражнения
  • § 4. КОЛЬЦА
  • Простейшие свойства кольца.
  • Гомоморфизмы колец.
  • Подкольца.
  • Упражнения
  • § 5. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
  • Изоморфизмы алгебраических систем.
  • Подсистемы.
  • Упражнения
    Глава четвертая. ОСНОВНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ
  • § 1. СИСТЕМА НАТУРАЛЬНЫХ ЧИСЕЛ
  • Слова в однобуквенном алфавите.
  • Система натуральных чисел.
  • Принцип математической индукции.
  • Упражнения
  • § 2. СВОЙСТВА СЛОЖЕНИЯ И УМНОЖЕНИЯ НАТУРАЛЬНЫХ ЧИСЕЛ
  • Свойства умножения.
  • § 3. ОТНОШЕНИЕ ПОРЯДКА НА МНОЖЕСТВЕ НАТУРАЛЬНЫХ ЧИСЕЛ
  • Полная упорядоченность множества натуральных чисел.
  • Упражнения
  • § 4. КОЛЬЦО ЦЕЛЫХ ЧИСЕЛ
  • Естественное умножение в аддитивной группе целых чисел.
  • Кольцо целых чисел.
  • Отношение делимости в кольце целых чисел.
  • Упражнения
  • § 5. ПОЛЯ. ПОЛЕ РАЦИОНАЛЬНЫХ ЧИСЕЛ
  • Поле рациональных чисел.
  • Упражнения
  • § 6. СИСТЕМА ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ
  • Система действительных чисел.
  • Упражнения
  • § 7. ПОЛЕ КОМПЛЕКСНЫХ ЧИСЕЛ
  • Поле комплексных чисел.
  • Модуль комплексного числа.
  • Геометрическое представление комплексных чисел.
  • Упражнения
  • § 8. ТРИГОНОМЕТРИЧЕСКАЯ ФОРМА КОМПЛЕКСНОГО ЧИСЛА. ИЗВЛЕЧЕНИЕ КОРНЕЙ ИЗ КОМПЛЕКСНЫХ ЧИСЕЛ
  • Корни n-й степени из единицы.
  • Корни n-й степени из произвольного комплексного числа.
  • Упражнения
    Глава пятая. АРИФМЕТИЧЕСКИЕ ВЕКТОРНЫЕ ПРОСТРАНСТВА И СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ
  • § 1. АРИФМЕТИЧЕСКИЕ ВЕКТОРНЫЕ ПРОСТРАНСТВА
  • Линейная зависимость и независимость системы векторов.
  • Эквивалентные системы векторов.
  • Базис конечной системы векторов.
  • Ранг конечной системы векторов.
  • Упражнения
  • § 2. СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ
  • Равносильные системы линейных уравнений и элементарные преобразования системы.
  • Равенство строчечного и столбцового рангов матрицы.
  • Связь между решениями неоднородной линейной системы и решениями ассоциированной с ней однородной системы.
  • Теоремы о следствиях системы линейных уравнений.
  • Упражнения.
  • § 3. СТУПЕНЧАТЫЕ МАТРИЦЫ И СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ
  • Приведенные ступенчатые матрицы.
  • Однородные системы линейных уравнений.
  • Фундаментальная система решений.
  • Решение системы линейных уравнений методом последовательного исключения переменных.
  • Упражнения
    Глава шестая. МАТРИЦЫ И ОПРЕДЕЛИТЕЛИ
  • § 1. ОПЕРАЦИИ НАД МАТРИЦАМИ И ИХ СВОЙСТВА
  • Транспонирование произведения матриц.
  • Упражнения
  • § 2. ОБРАТИМЫЕ МАТРИЦЫ
  • Элементарные матрицы.
  • Вычисление обратной матрицы.
  • Запись и решение системы n линейных уравнений с n переменными в матричной форме.
  • Упражнения
  • § 3. ПОДСТАНОВКИ
  • Четные и нечетные подстановки.
  • Знак подстановки.
  • Упражнения
  • § 4. ОПРЕДЕЛИТЕЛИ
  • Основные свойства определителей.
  • Упражнения
  • § 5. МИНОРЫ И АЛГЕБРАИЧЕСКИЕ ДОПОЛНЕНИЯ. ТЕОРЕМЫ ОБ ОПРЕДЕЛИТЕЛЯХ
  • Разложение определителя по строке или столбцу.
  • Определитель произведения матриц.
  • Необходимые и достаточные условия равенства нулю определителя.
  • § 6. ТЕОРЕМЫ О МАТРИЦАХ. ПРАВИЛО КРАМЕРА
  • Правило Крамера.
  • Условия, при которых система n линейных однородных уравнений с n переменными имеет ненулевые решения.
  • Упражнения
    Глава седьмая. ВЕКТОРНЫЕ ПРОСТРАНСТВА
  • § 1. ВЕКТОРНЫЕ ПРОСТРАНСТВА
  • Простейшие свойства векторных пространств.
  • Линейная зависимость и независимость системы векторов.
  • Упражнения
  • § 2. ПОДПРОСТРАНСТВА ВЕКТОРНОГО ПРОСТРАНСТВА
  • Линейная оболочка множества векторов.
  • Сумма подпространств.
  • Линейные многообразия.
  • Упражнения
  • § 3. БАЗИС И РАЗМЕРНОСТЬ ВЕКТОРНОГО ПРОСТРАНСТВА
  • Дополнение независимой системы векторов до базиса.
  • Размерность векторного пространства.
  • Упражнения.
  • § 4. ИЗОМОРФИЗМЫ ВЕКТОРНЫХ ПРОСТРАНСТВ
  • Изоморфизм векторных пространств.
  • Упражнения
  • § 5. ВЕКТОРНЫЕ ПРОСТРАНСТВА СО СКАЛЯРНЫМ УМНОЖЕНИЕМ
  • Ортогональная система векторов.
  • Процесс ортогонализации.
  • Упражнения.
  • § 6. ЕВКЛИДОВЫ ВЕКТОРНЫЕ ПРОСТРАНСТВА
  • Норма вектора.
  • Ортонормированный базис евклидова пространства.
  • Изоморфизмы евклидовых пространств.
  • Упражнения.
    Глава восьмая. ЛИНЕЙНЫЕ ОПЕРАТОРЫ
  • § 1. ЛИНЕЙНЫЕ ОТОБРАЖЕНИЯ
  • Ядро и образ линейного оператора.
  • Операции над линейными отображениями.
  • Упражнения
  • § 2. ПРЕДСТАВЛЕНИЕ ЛИНЕЙНЫХ ОПЕРАТОРОВ МАТРИЦАМИ
  • Связь между координатными столбцами векторов х и ф(x).
  • Ранг линейного оператора.
  • Связь между координатными столбцами вектора относительно различных базисов.
  • Связь между матрицами линейного оператора относительно различных базисов.
  • Упражнения
  • § 3. ЛИНЕЙНЫЕ АЛГЕБРЫ
  • Алгебра линейных операторов векторного пространства
  • Изоморфизм алгебры линейных операторов и полной матричной алгебры.
  • Упражнения
  • § 4. ОБРАТИМЫЕ ОПЕРАТОРЫ
  • Полная линейная группа.
  • Упражнения
  • § 5. СОБСТВЕННЫЕ ВЕКТОРЫ И СОБСТВЕННЫЕ ЗНАЧЕНИЯ. ХАРАКТЕРИСТИЧЕСКИЕ УРАВНЕНИЯ
  • Нахождение собственных векторов линейного оператора.
  • Характеристическое уравнение.
  • Линейные операторы с простым спектром.
  • Условия, при которых матрица подобна диагональной матрице.
  • Упражнения
    Глава девятая. СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ
  • § 1. СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ
  • Однородные системы линейных неравенств и выпуклые конусы.
  • Следствия однородной системы линейных неравенств.
  • Теорема Минковского.
  • Критерий несовместности системы линейных неравенств.
  • Неотрицательные решения системы линейных уравнений и системы линейных неравенств.
  • Упражнения
  • § 2. СТАНДАРТНЫЕ И КАНОНИЧЕСКИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ТЕОРЕМЫ ДВОЙСТВЕННОСТИ
  • Допустимые и оптимальные векторы.
  • Теорема двойственности для стандартных задач.
  • Теорема двойственности для канонических задач.
  • Теорема равновесия.
  • Упражнения
  • § 3. СИМПЛЕКС-МЕТОД
  • Упражнения
    Глава десятая. ГРУППЫ
  • § 1. ПОЛУГРУППЫ И МОНОИДЫ
  • Моноиды.
  • Обобщенный закон ассоциативности.
  • Упражнения
  • § 2. ПОДГРУППЫ И СМЕЖНЫЕ КЛАССЫ
  • Смежные классы.
  • Теорема Лагранжа.
  • Упражнения
  • § 3. ЦИКЛИЧЕСКИЕ ГРУППЫ
  • Циклические группы.
  • Подгруппы циклической группы.
  • Упражнения
  • § 4. НОРМАЛЬНЫЕ ДЕЛИТЕЛИ И ФАКТОР-ГРУППЫ
  • Фактор-группа.
  • Ядро гомоморфизма.
  • Упражнения
    Глава одиннадцатая. ТЕОРИЯ ДЕЛИМОСТИ В КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ
  • § 1. РАЗЛОЖЕНИЕ ЦЕЛЫХ ЧИСЕЛ НА ПРОСТЫЕ МНОЖИТЕЛИ
  • Простые числа.
  • Разложение целых чисел на простые множители.
  • Делители целого числа.
  • Число и сумма натуральных делителей числа.
  • Бесконечность множества простых чисел.
  • Решето Эратосфена.
  • Упражнения
  • § 2. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ И НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ
  • Взаимно простые числа.
  • Наименьшее общее кратное.
  • Упражнения
  • § 3. АЛГОРИТМ ЕВКЛИДА И КОНЕЧНЫЕ ЦЕПНЫЕ ДРОБИ
  • Конечные цепные дроби.
  • Подходящие дроби.
  • Упражнения.
  • § 4. ЦЕЛЫЕ СИСТЕМАТИЧЕСКИЕ ЧИСЛА
  • Арифметические операции над целыми систематическими числами
  • Перевод чисел из одной системы счисления в другую.
  • Упражнения
  • § 5. РАСПРЕДЕЛЕНИЕ ПРОСТЫХ ЧИСЕЛ
  • Функции T(х) и Л(х).
  • Неравенства для функции Т(х).
  • Неравенства Чебышева.
  • Простые числа в арифметических прогрессиях.
  • Упражнения
    Глава двенадцатая. ТЕОРИЯ СРАВНЕНИЙ С АРИФМЕТИЧЕСКИМИ ПРИЛОЖЕНИЯМИ
  • § 1. СРАВНЕНИЯ И ИХ СВОЙСТВА
  • Упражнения
  • § 2. ПОЛНАЯ СИСТЕМА ВЫЧЕТОВ
  • Упражнения
  • § 3. ПРИВЕДЕННАЯ СИСТЕМА ВЫЧЕТОВ
  • Мультипликативная группа классов вычетов, взаимно простых с модулем.
  • Функция Эйлера.
  • Теоремы Эйлера и Ферма.
  • Упражнения
  • § 4. СРАВНЕНИЯ ПЕРВОЙ СТЕПЕНИ. СРАВНЕНИЯ ВЫСШИХ СТЕПЕНЕЙ ПО ПРОСТОМУ МОДУЛЮ
  • Сравнения первой степени.
  • Сравнения высших степеней по простому модулю.
  • Упражнения
  • § 5. ПЕРВООБРАЗНЫЕ КОРНИ И ИНДЕКСЫ
  • Первообразные корни по простому модулю.
  • Индексы по простому модулю.
  • Двучленные сравнения.
  • Упражнения
  • § 6. ОБРАЩЕНИЕ ОБЫКНОВЕННОЙ ДРОБИ В СИСТЕМАТИЧЕСКУЮ И ОПРЕДЕЛЕНИЕ ДЛИНЫ ПЕРИОДА СИСТЕМАТИЧЕСКОЙ ДРОБИ
  • Упражнения
    Глава тринадцатая. КОЛЬЦА
  • § 1. ИДЕАЛЫ КОЛЬЦА. ФАКТОР-КОЛЬЦО
  • Сравнения и классы вычетов по идеалу.
  • Фактор-кольцо.
  • Теорема об эпиморфизмах колец.
  • Характеристика кольца.
  • Наименьшее подкольцо кольца.
  • Упражнения
  • § 2. ПОЛЕ ЧАСТНЫХ ОБЛАСТИ ЦЕЛОСТНОСТИ
  • Изоморфизм полей частных.
  • Упражнения
  • § 3. КОЛЬЦА ГЛАВНЫХ ИДЕАЛОВ
  • Простые и составные элементы области целостности.
  • Кольца главных идеалов.
  • Факториальность кольца главных идеалов.
  • Евклидовы кольца.
  • Упражнения
  • § 4. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ. НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ
  • Наименьшее общее кратное.
  • Упражнения
    Глава четырнадцатая. ПОЛИНОМЫ ОТ ОДНОЙ ПЕРЕМЕННОЙ
  • § 1. КОЛЬЦО ПОЛИНОМОВ
  • Теорема о существовании простого трансцендентного расширения коммутативного кольца.
  • Степень полинома.
  • Деление полинома на двучлен и корни полинома.
  • Теорема о наибольшем возможном числе корней полинома в области целостности.
  • Алгебраическое и функциональное равенства полиномов.
  • Упражнения
  • § 2. ПОЛИНОМЫ НАД ПОЛЕМ
  • Алгоритм Евклида.
  • Неприводимые над данным полем полиномы.
  • Разложение полинома в произведение нормированных неприводимых множителей.
  • Упражнения
  • § 3. ФАКТОРИАЛЬНОСТЬ КОЛЬЦА ПОЛИНОМОВ НАД ФАКТОРИАЛЬНЫМ КОЛЬЦОМ
  • Факториальность кольца полиномов.
  • § 4. ФОРМАЛЬНАЯ ПРОИЗВОДНАЯ ПОЛИНОМА. НЕПРИВОДИМЫЕ КРАТНЫЕ МНОЖИТЕЛИ
  • Разложение полинома по степеням разности х — с.
  • Неприводимые кратные множители полинома.
  • Кратные корни полинома.
  • Упражнения
    Глава пятнадцатая. ПОЛИНОМЫ ОТ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ
  • § 1. КОЛЬЦО ПОЛИНОМОВ ОТ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ
  • Кольцо полиномов от нескольких переменных.
  • Изоморфизм колец полиномов.
  • Нормальное представление полинома и степень полинома.
  • Факториалыюсть кольца полиномов.
  • § 2. СИММЕТРИЧЕСКИЕ ПОЛИНОМЫ
  • Лемма о высшем члене произведения двух полиномов.
  • Симметрические полиномы.
  • Леммы о симметрических полиномах.
  • Основная теорема о симметрических полиномах.
  • Упражнения
  • 3. РЕЗУЛЬТАНТ ПОЛИНОМОВ И ИСКЛЮЧЕНИЕ ПЕРЕМЕННЫХ
  • Исключение переменных.
    Глава шестнадцатая. ПОЛИНОМЫ НАД ПОЛЕМ КОМПЛЕКСНЫХ ЧИСЕЛ И НАД ПОЛЕМ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ
  • § 1. АЛГЕБРАИЧЕСКАЯ ЗАМКНУТОСТЬ ПОЛЯ КОМПЛЕКСНЫХ ЧИСЕЛ
  • Непрерывность модуля полинома.
  • Наименьшее значение модуля полинома.
  • Лемма Даламбера.
  • Алгебраическая замкнутость поля комплексных чисел.
  • Формулы Виета.
  • Упражнения
  • § 2. ПОЛИНОМЫ НАД ПОЛЕМ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ
  • § 3. УРАВНЕНИЯ ТРЕТЬЕЙ И ЧЕТВЕРТОЙ СТЕПЕНИ
  • Исследование корней уравнения третьей степени с действительными коэффициентами.
  • Уравнения четвертой степени.
  • § 4. ОТДЕЛЕНИЕ ДЕЙСТВИТЕЛЬНЫХ КОРНЕЙ ПОЛИНОМА
  • Теорема Штурма.
    Глава семнадцатая. ПОЛИНОМЫ НАД ПОЛЕМ РАЦИОНАЛЬНЫХ ЧИСЕЛ И АЛГЕБРАИЧЕСКИЕ ЧИСЛА
  • § 1. ЦЕЛЫЕ И РАЦИОНАЛЬНЫЕ КОРНИ ПОЛИНОМА. КРИТЕРИЙ НЕПРИВОДИМОСТИ
  • § 2. ПРОСТОЕ АЛГЕБРАИЧЕСКОЕ РАСШИРЕНИЕ ПОЛЯ
  • § 3. СОСТАВНОЕ АЛГЕБРАИЧЕСКОЕ РАСШИРЕНИЕ ПОЛЯ
  • § 4. УСЛОВИЯ РАЗРЕШИМОСТИ УРАВНЕНИЯ ТРЕТЬЕЙ СТЕПЕНИ В КВАДРАТНЫХ РАДИКАЛАХ
  • ЛИТЕРАТУРА

Формулы и законы логики

На вводном уроке, посвящённом основам математической логики, мы познакомились с базовыми понятиями этого раздела математики, и сейчас тема получает закономерное продолжение. Помимо нового теоретического, а точнее даже не теоретического – а общеобразовательного материала нас ожидают практические задания, и поэтому если вы зашли на данную страницу с поисковика и/или плохо ориентируетесь в материале, то, пожалуйста, пройдите по вышеуказанной ссылке и начните с предыдущей статьи. Кроме того, для практики нам потребуется 5 таблиц истинности логических операций, которые я настоятельно рекомендую переписать от руки.

НЕ запомнить, НЕ распечатать, а именно ещё раз осмыслить и собственноручно переписать на бумагу – чтобы они были перед глазами:

– таблица НЕ;
– таблица И;
– таблица ИЛИ;
– импликационная таблица;
– таблица эквиваленции.

Это очень важно. В принципе, их было бы удобно занумеровать «Таблица 1», «Таблица 2» и т.д., но я неоднократно подчёркивал изъян такого подхода – как говорится, в одном источнике таблица окажется первой, а в другом – сто первой. Поэтому будем использовать «натуральные» названия. Продолжаем:

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

1) любые элементарные (простые) высказывания ;

2) если и – формулы, то формулами также являются выражения вида
.

Никаких других формул нет.

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

Формулой не является, например, запись – и здесь прослеживается очевидная аналогия с «алгебраическим мусором» , из которого не понятно – нужно ли числа складывать или умножать.

Логическую формулу можно рассматривать, как логическую функцию. Запишем в функциональном виде ту же конъюнкцию:

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

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

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

– в первую очередь выполняется отрицание ;
– во вторую очередь – конъюнкция ;
– затем – дизъюнкция ;
– потом импликация ;
– и, наконец, низший приоритет имеет эквиваленция .

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

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

Наверное, все понимают, но на всякий пожарный: и – это две разные формулы! (как в формальном, так и в содержательном плане)

Составим таблицу истинности для формулы . В данную формулу входят два элементарных высказывания и «на входе» нам нужно перечислить все возможные комбинации единиц и нулей. Чтобы избежать путаницы и разночтений договоримся перечислять комбинации строго в таком порядке (который я, собственно, де-факто использую с самого начала):
В формулу входят две логические операции, и согласно их приоритету, в первую очередь нужно выполнить отрицание высказывания . Ну что же, отрицаем столбец «пэ» – единицы превращаем в нули, а нули – в единицы:
На втором шаге смотрим на столбцы и и применяем к ним операцию ИЛИ. Немного забегая вперёд, скажу, что дизъюнкция перестановочна ( и – это одно и то же), и поэтому столбцы можно анализировать в привычном порядке – слева направо. При выполнении логического сложения удобно использовать следующее прикладное рассуждение: «Если два нуля – ставим ноль, если хотя бы одна единица – единицу»:
Таблица истинности построена. А теперь вспомним старую-добрую импликацию:
…внимательно-внимательно… смотрим на итоговые колонки…. В алгебре высказываний такие формулы называются равносильными или тождественными:

(три горизонтальные чёрточки – это значок тождества)

В 1-й части урока я обещал выразить импликацию через базовые логические операции, и выполнение обещания не заставило себя ждать! Желающие могут вложить в импликацию содержательный смысл (например, «Если идёт дождь, то на улице сыро») и самостоятельно проанализировать равносильное утверждение .

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

Задание 1

Составить таблицу истинности для формулы и убедиться в справедливости знакомого вам тождества .

Ещё раз повторим порядок решения задачи:

1) Так как в формулу входят две переменные, то всего будет 4 возможных набора нулей и единиц. Записываем их в оговорённом выше порядке.

2) Импликации «слабее» конъюнкции, но они располагаются в скобках. Заполняем столбец , при этом удобно использовать следующее прикладное рассуждение: «если из единицы следует ноль, то ставим ноль, во всех других случаях – единицу». Далее заполняем столбец для импликации , и при этом, внимание! – столбцы и следует анализировать «справа налево»!

3) И на завершающем этапе заполняем итоговый столбец . А здесь удобно рассуждать так: «если в столбцах и две единицы, то ставим единицу, во всех остальных случаях – ноль».

И, наконец, сверяемся с таблицей истинности эквиваленции .

Основные равносильности алгебры высказываний

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

Коммутативность конъюнкции и коммутативность дизъюнкции

Коммутативность – это перестановочность:

Знакомые с 1-го класса правила: «От перестановки множителей (слагаемых) произведение (сумма) не меняется». Но при всей кажущейся элементарности этого свойства, справедливо оно далеко не всегда, в частности, некоммутативным является умножение матриц (в общем случае их переставлять нельзя), а векторное произведение векторов – антикоммутативно (перестановка векторов влечёт за собой смену знака).

И, кроме того, здесь я снова хочу подчеркнуть формализм математической логики. Так, например, фразы «Студент сдал экзамен и выпил» и «Студент выпил и сдал экзамен» различны с содержательной точки зрения, но неразличимы с позиций формальной истинности. …Таких студентов знает каждый из нас, и из этических соображений мы не будет озвучивать конкретных имён =)

Ассоциативность логического умножения и сложения

Или, если «по-школьному» – сочетательное свойство:

Дистрибутивные свойства

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

И опять же – эти, казалось бы, «банальные» свойства выполняются далеко не во всех алгебраических системах, и, более того, требуют доказательства (о которых мы очень скоро поговорим). К слову, второй дистрибутивный закон несправедлив даже в нашей «обычной» алгебре. И в самом деле:

Закон идемпотентности

Что делать, латынь….

Прямо какой-то принцип здоровой психики: «я и я – это я», «я или я – это тоже я» =)

И тут же несколько похожих тождеств:

…мда, что-то я даже подзавис… так и доктором философии завтра можно проснуться =)

Закон двойного отрицания

Ну а здесь уже напрашивается пример с русским языком – все прекрасно знают, что две частицы «не» означают «да». А для того, чтобы усилить эмоциональную окраску отрицания нередко используют три «не»:
– даже с крохотным доказательством получилось!

Законы поглощения

– «а был ли мальчик?» =)

В правом тождестве скобки можно опустить.

Законы де Моргана

Предположим, что строгий Преподаватель (имя которого вам тоже известно:)) ставит экзамен, если – Студент ответил на 1-й вопрос и – Студент ответил на 2-й вопрос. Тогда высказывание , гласящее о том, что Студент не сдал экзамен, будет равносильно утверждению – Студент не ответил на 1-й вопрос или на 2-й вопрос.

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

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

Да, это доказательство является примитивным (а кто-то скажет, что и «тупым»), но типичный Преподаватель по матлогике вытрясет за него душу. Поэтому даже к таким простым вещам не стОит относиться пренебрежительно.

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

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

Любую равносильность можно представить в виде тождественно истинной формулы . Это значит, что ПРИ ЛЮБОМ исходном наборе нулей и единиц «на выходе» получается строго единица. И этому есть очень простое объяснение: так как таблицы истинности и совпадают, то, разумеется, они эквивалентны. Соединим, например, эквиваленцией левую и правую часть только что доказанного тождества де Моргана:
Или, если компактнее:

Задание 2

Доказать следующие равносильности:

а) ;

б)

Краткое решение в конце урока. Не ленимся! Постарайтесь не просто составить таблицы истинности, но ещё и чётко сформулировать выводы. Как я недавно отмечал, пренебрежение простыми вещами может обойтись очень и очень дорого!

Продолжаем знакомиться с законами логики!

Да, совершенно верно – мы с ними уже вовсю работаем:

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

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

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

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

Доказательство тривиально:
«На выходе» получены исключительно нули, следовательно, формула действительно тождественна ложна.

Однако и любое противоречие – это тоже закон логики, в частности:

Нельзя объять столь обширную тему в одной-единственной статье, и поэтому я ограничусь ещё лишь несколькими законами:

Закон исключённого третьего

– в классической логике любое высказывание истинно или ложно и третьего не дано. «Быть или не быть» – вот в чём вопрос.

Самостоятельно составьте табличку истинности и убедитесь в том, что это тождественно истинная формула.

Закон контрапозиции

Этот закон активно муссировался, когда мы обсуждали суть необходимого условия, вспоминаем: «Если во время дождя на улице сыро, то из этого следует, что если на улице сухо, то дождя точно не было».

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

Если истинна обратная теорема , то в силу закона контрапозиции , справедлива и теорема, противоположная обратной:

И снова вернёмся к нашим содержательным примерам: для высказываний – число делится на 4, – число делится на 2 справедливы прямая и противоположная теоремы, но ложны обратная и противоположная обратной теоремы. Для «взрослой» же формулировки теоремы Пифагора истинны все 4 «направления».

Закон силлогизма

Тоже классика жанра: «Все дубы – деревья, все деревья – растения, следовательно, все дубы – растения».

Ну и здесь опять хочется отметить формализм математической логики: если наш строгий Преподаватель думает, что некий Студент – есть дуб, то с формальной точки зрения данный Студент, безусловно, растение =) …хотя, если задуматься, то может быть и с неформальной тоже =)

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

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

1) выполняем импликации и . Вообще говоря, можно сразу выполнить и 3-ю импликацию, но с ней удобнее (и допустимо!) разобраться чуть позже;

2) к столбцам применяем правило И;

3) вот теперь выполняем ;

4) и на завершающем шаге применяем импликацию к столбцам и .

Не стесняйтесь контролировать процесс указательным и средним пальцем :))
Из последнего столбца, думаю, всё понятно без комментариев:
, что и требовалось доказать.

Задание 3

Выяснить, будет ли являться законом логики следующая формула:

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

Преобразование логических формул

Помимо своего «логического» назначения, равносильности широко используются для преобразования и упрощения формул. Грубо говоря, одну часть тождества можно менять на другую. Так, например, если в логической формуле вам встретился фрагмент , то по закону идемпотентности вместо него можно (и нужно) записать просто . Если вы видите , то по закону поглощения упрощайте запись до . И так далее.

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

, где – любые (сколь угодно сложные) формулы.

Преобразуем, например, сложную импликацию (1-е тождество):

Далее применим к скобке «сложный» закон де Моргана, при этом, в силу приоритета операций, именно закон , где :

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

Далее напрашивается использовать «простой» закон де Моргана и т.д.

Ну, а с коммутативностью вообще всё просто – даже обозначать ничего не нужно… что-то запал мне в душу закон силлогизма:))

Таким образом, закон можно переписать и в более затейливом виде:

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

В качестве тренировки упросим формулу .

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

Как правило, на первом шаге (шагах) избавляются от эквиваленции и импликации (если они есть) и сводят формулу к трём основным логическим операциям. Что тут скажешь…. Логично.

(1) Используем тождество . А нашем случае .

Затем обычно следуют «разборки» со скобками. Сначала всё решение, затем комментарии. Чтобы не получилось «масло масляное», буду использовать значки «обычного» равенства:

(2) К внешним скобкам применяем закон де Моргана , где .

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

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

(5) В силу коммутативности дизъюнкции меняем местами и , а также и .
(6) Используем закон идемпотентности и закон исключенного третьего

(7) Дважды используем тождество

Вот оно как…, оказалось, что наша формула – тожественно истинна:

Желающие могут составить таблицу истинности и убедиться в справедливости данного факта.

Наверное, все обратили внимание на формализм последних преобразований, но решать лучше именно так! В противном случае с немалой вероятностью гарантированы проблемы с зачётом задания (впрочем, тут от преподавателя зависит). Математическая логика как наука – формальна, и строго говоря, осуществлять «перескоки» наподобие нежелательно.

Пара задач для закрепления материала:

Задание 4

Выразить эквиваленцию через отрицание, конъюнкцию, дизъюнкцию и раскрыть скобки

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

Задание 5

Упростить логическую формулу

Решения с подробными комментариями совсем близко.

И в заключение урока небольшое напутствие для читателей, которым предстоит погружение в матлогику. Данный предмет у меня был на 1-м курсе института, и в ходе изучения исчисления высказываний, предикатов и прочих «машин тьюринга» я допускал принципиальную ошибку – а именно, пытался «подогнать» под математическую логику неформальную основу. И окончательное понимание всей стройности формальной теории, важности «очевидных» доказательств и т.д. пришло далеко не сразу. Скучно? Нет! – на самом деле очень красиво…. То же самое, кстати, относится к высшей алгебре и некоторым другим предметам.

…но что бы вы прочитали эти строки, я всё-таки преподнёс материал, скорее в «школьном» стиле – с многочисленными содержательными примерами!

Желаю успехов!

Решения и ответы:

Задание 1 Решение: составим таблицу истинности для формулы :
(подробные инструкции по заполнению таблицы находятся после условия задачи)
Полученный результат совпадает с эквиваленцией высказываний и , таким образом:

Задание 2 Решение: доказательства проведём с помощью таблиц истинности:

а) Дважды записываем все варианты истины и лжи высказывания и применяем к столбцам операцию ИЛИ:
Результат совпадает с . Тождество доказано

б) составим таблицу истинности для левой части тождества
. Сначала к столбцам и применяем операцию ИЛИ, затем к столбцам и – операцию И:
В результате истинность формулы совпала с истинностью высказывания , таким образом, тождество доказано.

Задание 3 Решение: составим таблицу истинности:
Вывод: данная формула не является тождественно истинной (законом логики)

Задание 4 Решение:

(1) Используем тождество .
(2) Дважды применяем тождество .
(3) Используем дистрибутивный закон , в данном случае:
(квадратные скобки можно было не ставить – они не меняют порядок действий, но помогают лучше видеть ситуацию).
(4) В квадратных скобках используем коммутативность конъюнкции.
(5) Дважды используем тот же самый дистрибутивный закон.
(6) Во второй слева скобке используем коммутативность конъюнкции.
(7) Согласно закону противоречия: .
(8) К формуле дважды применяем тожество .
(9) А это уже для красоты :)) Скобки, кстати, можно было убрать намного раньше (я их не опускал с целью улучшить восприятие преобразований).

Примечание: на 3-м шаге можно было раскрыть скобки по «правилу умножения многочленов» и сразу перейти к шагу № 7, но, строго говоря, это действие ещё нужно обосновать. А вдруг в алгебре логики это правило несправедливо?

Задание 5 Решение:

(1) Для левой скобки используем закон де Моргана. Во второй скобке – «раскладываем» импликацию.
(2) В первой скобке дважды применяем закон двойного отрицания. В силу коммутативности конъюнкции меняем местам и .
(3) К «иксу» и правой скобке применяем дистрибутивный закон.
(4) Согласно закону противоречия высказывания, средняя скобка тождественно ложна.
(5) К левой скобке применяем тождество . Убираем все скобки, поскольку это не меняет порядок действий.
(6) Используем коммутативность умножения и закон поглощения .

Ответ:

Емелин Александр

Алгебра множеств

Алгеброй называется совокупность множества с заданными в нем операциями , где — носитель, — сигнатура.

Алгеброй множеств называется совокупность булеана универсального множества с заданными в нем операциями:

где — множество операций: пересечение, объединение, дополнение, разность.

Законы алгебры множеств

Для операций объединения, пересечения и дополнения выполняются следующие законы:

  1. коммутативности:
  2. ассоциативности:
  3. дистрибутивности:
    • пересечения относительно объединения:
    • объединение относительно пересечения:
  4. идемпотентности:
  5. действия с универсальным и пустым множествами:
  6. де Моргана:
  7. двойного дополнения:

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

Докажем закон дистрибутивности:

Графическое доказательство состоит в построении диаграмм Эйлера-Венна для правой и левой частей ( рис. 2.1).

Доказательство

Если и и или или .

Рис. 2.1.

Таким образом, . Необходимо доказать включение в обратную сторону:

или

или и и .

Следовательно, .

Докажем закон де Моргана

Графическая интерпретация представлена на рис. 2.2.

Рис. 2.2.

Рассмотрим графическую интерпретацию левой части закона де Моргана, в которой можно выделить три составные части ( рис. 2.3).

Рис. 2.3.

Используя закон идемпотентности , получим:

по закону дистрибутивности

Таким образом, .

Аналогично доказывается включение в обратную сторону:

Следовательно,

Законы логики на уроках информатики и ИКТ

Урок по информатике рассчитан на учащихся 10-х классов общеобразовательной школы, в учебном плане которой входит раздел «Алгебра логики». Учащимся очень нелегко дается эта тема, поэтому мне, как учителю, захотелось заинтересовать их в изучении законов логики, упрощении логических выражений и с интересом подойти к решению логических задач. В обычной форме давать уроки по этой теме нудно и хлопотно, да и ребятам не всегда понятны некоторые определения. В связи с предоставлением информационного пространства, у меня появилась возможность выкладывать свои уроки в оболочке «learning». Учащиеся, зарегистрировавшись в ней, могут в свое свободное время посещать этот курс и перечитывать то, что было непонятно на уроке. Некоторые учащиеся, пропустив уроки по болезни, наверстывают дома или в школе пропущенную тему и всегда готовы к следующему уроку. Такая форма преподавания очень устроила многих ребят и те законы, которые им были непонятны, теперь в компьютерном виде ими усваиваются гораздо легче и быстрее. Предлагаю один из таких уроков информатики, который проводится интегративно с ИКТ.

План урока

  1. Объяснение нового материала, с привлечением компьютера – 25 минут.
  2. Основные понятия и определения, выложенные в «learning» — 10 минут.
  3. Материал для любознательных – 5 минут.
  4. Домашнее задание – 5 минут.

1. Объяснение нового материала

Законы формальной логики

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

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

Закон тождества: в процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе.

Закон непротиворечия: невозможно, чтобы одно и то оке в одно то же время было и не было присуще одному и тому же в одном и том же отношении. То есть невозможно что-либо одновременно утверждать и отрицать.

Закон исключенного третьего: из двух противоречащих суждений одно истинно, другое ложно, а третьего не дано.

Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована.

Последний закон говорит о том, что доказательство чего-либо предполагает обоснование именно и только истинных мыслей. Ложные же мысли доказать нельзя. Есть хорошая латинская пословица: «Ошибаться свойственно всякому человеку, но настаивать на ошибке свойственно только глупцу». Формулы этого закона нет, так как он имеет только содержательный характер. В качестве аргументов для подтверждения истинной мысли могут быть использованы истинные суждения, фактический материал, статистические данные, законы науки, аксиомы, доказанные теоремы.

Законы алгебры высказываний

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

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

Законы алгебры высказываний (алгебры логики) — это тавтологии.

Иногда эти законы называются теоремами.

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

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

Закон тождества:

А=А

Всякое понятие и суждение тождественно самому себе.

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

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

В рассуждении: Движение вечно. Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемещению в пространстве), что приводит к ложному выводу.

Закон непротиворечия:

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

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

Иногда этот закон формулируется так: два противоречащих друг другу высказывания не могут быть одновременно истинными. Примеры невыполнения закона непротиворечия:

1. На Марсе есть жизнь и на Марсе жизни нет.

2. Оля окончила среднюю школу и учится в X классе.

Закон исключенного третьего:

В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А. Примеры выполнения закона исключенного третьего:

1. Число 12345 либо четное, либо нечетное, третьего не дано.

2. Предприятие работает убыточно или безубыточно.

3. Эта жидкость является или не является кислотой.

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

Рассмотрим следующее высказывание: Это предложение ложно. Оно не может быть истинным, потому что в нем утверждается, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нарушается закон исключенного третьего.

Парадокс (греч. paradoxos — неожиданный, странный) в этом примере возникает из-за того, что предложение ссылается само на себя. Другим известным парадоксом является задача о парикмахере: В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру? В логике из-за ее формальности нет возможности получить форму такого ссылающегося самого на себя высказывания. Это еще раз подтверждает мысль о том, что с помощью алгебры логики нельзя выразить все возможные мысли и доводы. Покажем, как на основании определения эквивалентности высказываний могут быть получены остальные законы алгебры высказываний.

Например, определим, чему эквивалентно (равносильно) А (двойное отрицание А, т. е. отрицание отрицания А). Для этого построим таблицу истинности:

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

Таким образом, мы можем сформулировать закон двойного отрицания:

Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. Например, высказывание А = Матроскин — кот эквивалентно высказыванию А = Неверно, что Матроскин не кот.

Аналогичным образом можно вывести и проверить следующие законы:

Свойства констант:

Законы идемпотентности:

Сколько бы раз мы ни повторяли: телевизор включен или телевизор включен или телевизор включен … значение высказывания не изменится. Аналогично от повторения на улице тепло, на улице тепло,… ни на один градус теплее не станет.

Законы коммутативности:

A v B = B v A

А & В = В & А

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

Законы ассоциативности:

A v(B v C) = (A v B) v C;

А & (В & C) = (A & В) & С.

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

Законы дистрибутивности:

A v (B & C) = (A v B) &(A v C)

(дистрибутивность дизъюнкции
относительно конъюнкции)

А & (B v C) = (A & B) v (А & C)

(дистрибутивность конъюнкции
относительно дизъюнкции)

Закон дистрибутивности конъюнкции относительно дизъюнкции ана­логичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее всего провести с помощью таблицы истинности:

Законы поглощения:

A v (A & B) = A

A & (A v B) = A

Проведите доказательство законов поглощения самостоятельно.

Законы де Моргана:

Словесные формулировки законов де Моргана:

Мнемоническое правило: в левой части тождества операция отрицания стоит над всем высказыванием. В правой части она как бы разрывается и отрицание стоит над каждым из простых высказываний, но одновременно меняется операция: дизъюнкция на конъюнкцию и наоборот.

Примеры выполнения закона де Моргана:

1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка.

2) Высказывание Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

Замена операций импликации и эквивалентности

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

Так, заменить операцию импликации можно в соответствии со следующим правилом:

Для замены операции эквивалентности существует два правила:

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

Знание правил замены операций импликации и эквивалентности помогает, например, правильно построить отрицание импликации.

Рассмотрим следующий пример.

Пусть дано высказывание:

Е = Неверно, что если я выиграю конкурс, то получу приз.

Пусть А = Я выиграю конкурс,

В = Я получу приз.

Тогда

Отсюда, Е = Я выиграю конкурс, но приз не получу.

Интерес представляют и следующие правила:

Доказать их справедливость можно также с помощью таблиц истинности.

Интересно их выражение на естественном языке.

Например, фраза

Если Винни-Пух съел мед, то он сыт

тождественна фразе

Если Винни-Пух не сыт, то меда он не ел.

Задание: придумайте фразы-примеры на данные правила.

2. Основные понятия и определения в Приложении 1

3. Материал для любознательных в Приложении 2

4. Домашнее задание

1) Выучить законы логики, используя курс «Алгебры логики», размещенный в информационном пространстве (www.learning.9151394.ru).

2) Проверить на ПК доказательство законов де Моргана, построив таблицу истинности.

Приложения

  1. Основные понятия и определения (Приложение 1).
  2. Материал для любознательных (Приложение 2).

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *