Порядок действий в математической логике

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

Для определения истинности или ложности результатов логических операций пользуются таблицами истинности, где ИСТИНА и ЛОЖЬ обозначаются 1 и 0. Для логического сложения таблица истинности выглядит так:

II. Логическое умножение (конъюнкция).

Объединение простых высказываний союзом И, называют логическим умножением или конъюнкцией.Обозначают:

Для логического умножения таблица истинности выглядит так:

III. Логическое отрицание (инверсия).

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

Для логического отрицания таблица истинности выглядит так:

IV. Логическое следование (импликация).

Сложное логическое высказывание , образованное с помощью связки ‘ЕСЛИ. ТО. ‘ называют логическим следованием или импликацией. Обозначают:

Для логического следования таблица истинности выглядит так:

V. Логическое равенство (эквивалентность).

Сложное логическое высказывание , образованное с помощью связки ‘ТОГДА И ТОЛЬКО ТОГДА. ‘ называют логическим равенством или эквивалентностью. Равнозначность называют также эквиваленцией. Обозначают:

Для логического равенства таблица истинности выглядит так:

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

Для логических операций порядок выполнения в заданной логической функции (составного высказывания) выглядит так:

Законы математической логики.

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

Виды задач по математической логике.

Составьте таблицу истинности для заданной функции:

Составим таблицу истинности для всех возможных значений высказываний, входящих в заданную функцию. Количество всех возможных значений определяется по формуле: 2 n , где n — количество входящих в функцию высказываний. Т.к. у нас в функцию входит только 2 высказывания — А и В, то возможных значений будет 2 2 = 4. Упрощаем работу, находя значения истинности функции по действиям. Порядок действий при этом надо соблюдать! Он как в математике:

Докажите равенство логических выражений с помощью таблиц истинности:

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

Сравним результаты в последних колонках. Если результаты совпали, то и функции равны.

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

Определите при каких значениях выражений заданная функция ложна:

1 способ: Составим полную таблицу истинности функции, как в 1 задаче:

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

2 способ: Заданная функция ложна только тогда, когда оба слогаемых ложны. Слогаемое ¬ (A / B) — ложно, если (A / B) — истинно. Произведение истинно, если оба сомножителя истинны, т. е. А=1 и В=1.

Ответ: при A=1 , B=1

Докажите равенство логических выражений с помощью законов математической логики:

Упращаем левое логическое выражение, пользуясь законами математической логики: непротиворечия и исключённого третьего

В результате пришли к виду правого логического выражения.

Конъюнкция или логическое умножение (в теории множеств – это пересечение)

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

Обозначение: &, $wedge$, $cdot$.

Таблица истинности для конъюнкции

1. Если хотя бы одно из подвыражений конъюнкции ложно на некотором наборе значений переменных, то и вся конъюнкция будет ложной для этого набора значений.
2. Если все выражения конъюнкции истинны на некотором наборе значений переменных, то и вся конъюнкция тоже будет истинна.
3. Значение всей конъюнкции сложного выражения не зависит от порядка записи подвыражений, к которым она применяется (как в математике умножение).

Дизъюнкция или логическое сложение (в теории множеств это объединение)

Дизъюнкция является сложным логическим выражением, которое истинно практически всегда, за исключением, когда все выражения ложны.

Попробуй обратиться за помощью к преподавателям

Таблица истинности для дизъюнкции

1. Если хотя бы одно из подвыражений дизъюнкции истинно на некотором наборе значений переменных, то и вся дизъюнкция принимает истинное значение для данного набора подвыражений.
2. Если все выражения из некоторого списка дизъюнкции ложны на некотором наборе значений переменных, то и вся дизъюнкция этих выражений тоже ложна.
3. Значение всей дизъюнкции не зависит от порядка записи подвыражений (как в математике – сложение).

Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)

Отрицание — означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.

Задай вопрос специалистам и получи
ответ уже через 15 минут!

Обозначения: не $A$, $ar$, $¬A$.

Таблица истинности для инверсии

«Двойное отрицание» $¬¬A$ является следствием суждения $A$, то есть имеет место тавтология в формальной логике и равно самому значению в булевой логике.

Импликация или логическое следование

Импликация — это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть, данная логическая операция связывает два простых логических выражения, из которых первое является условием ($A$), а второе ($A$) является следствием условия ($A$).

Обозначения: $ o$, $Rightarrow$.

Таблица истинности для импликации

1. $A o B = ¬A vee B$.
2. Импликация $A o B$ ложна, если $A=1$ и $B=0$.
3. Если $A=0$, то импликация $A o B$ истинна при любом значении $B$, (из лжи может следовать истинна).

Эквивалентность или логическая равнозначность

Эквивалентность — это сложное логическое выражение, которое истинно на равных значениях переменных $A$ и $B$.

Обозначения: $leftrightarrow$, $Leftrightarrow$, $equiv$.

Таблица истинности для эквивалентности

Строгая дизъюнкция или сложение по модулю 2 ( в теории множеств это объединение двух множеств без их пересечения)

Строгая дизъюнкция истинна, если значения аргументов не равны.

Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных $1$, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

Обозначения: $A oplus B$ (в языках программирования), $A≠B$, $A wedge B$ (в языках программирования).

Таблица истинности для операции сложения по модулю два

Свойства строгой дизъюнкции:

Стрелка Пирса

Бинарная логическая операция, булева функция над двумя переменными. Названа в честь Чарльза Пирса и введена в алгебру логики в $1880—1881$ гг.

Обозначения: $downarrow$ , ИЛИ-НЕ

Таблица истинности для стрелки Пирса

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

$X downarrow X = ¬X$— отрицание

$(X downarrow Y) downarrow (X downarrow Y) equiv X vee Y$ — дизъюнкция

$(X downarrow X) downarrow (Y downarrow Y) equiv X wedge Y$ — конъюнкция

$((X downarrow X) downarrow Y) downarrow ((X downarrow X) downarrow Y) = X o Y$ — импликация

В электронике стрелка Пирса представлена в виде элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NОR).

Штрих Шеффера

Булева функция двух переменных или бинарная логическая операция. Введена в рассмотрение Генри Шеффером в 1913 г.

Обозначения: $|$, эквивалентно операции И-НЕ.

Таблицей истинности для функции штрих Шеффера

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

Для электроники это означает, что реализация схем возможна с использованием одного типового элемента (правда это дорогостоящий элемент).

Порядок выполнения логических операций в сложном логическом выражении

1. Инверсия(отрицание);
2. Конъюнкция (логическое умножение);
3. Дизъюнкция и строгая дизъюнкция (логическое сложение);
4. Импликация (следствие);
5. Эквивалентность (тождество).

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

Общие свойства

Для набора из $n$ логических переменных существует ровно $2^n$ различных значений. Таблица истинности для логического выражения от $n$ переменных содержит $n+1$ столбец и $2^n$ строк.

Так и не нашли ответ
на свой вопрос?

Просто напиши с чем тебе
нужна помощь

Высказывание (суждение) — это повествовательное предложение, в котором что-либо утверждается или отрицается. По поводу любого высказывания можно сказать, истинно оно или ложно. Например:

«Лед — твердое состояние воды» — истинное высказывание.

«Треугольник, это геометрическая фигура» — истинное выска­зывание.

«Париж — столица Китая» — ложное высказывание.

Обозначим через А простое высказывание «летом я поеду Я деревню», а через В — простое высказывание «летом я поеду в туристическую поездку». Тогда логическая форма сложного высказывания имеет вид

A В.

Пример 3. Рассмотрим высказывание: «Неверно, что 4 делится на 3».

Обозначим через А простое высказывание «4 делится на 3». Тогда логическая форма отрицания этого высказывания имеет вид А

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

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

Приложения математической логики в базовом курсе

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

Первое понятие о логической величине можно дать как ответ на альтернативный вопрос. Например: «Имеется ли данная книга в библиотеке?» или «Поступил ли абитуриент в университет», или «На улице идет дождь?» и т.п. Ответами на такие вопросы могут быть только «да» или «нет». Синонимами являются «истина», «ложь»; «true», «false». Если поле таблицы будет принимать только такие значения, то ему назначается логический тип.

Например, реляционная база данных ФАКУЛЬТАТИВЫ со­держит сведения о посещении учениками трех факультативов по геологии, цветоводству и танцам. На реляционном языке ее струк­тура описывается так:

ФАКУЛЬТАТИВЫ (УЧЕНИК. ГЕОЛОГИЯ, ЦВЕТОВОДСТВО, ТАНЦЫ)

Поля ГЕОЛОГИЯ, ЦВЕТОВОДСТВО и ТАНЦЫ будут иметь логический тип. Значение ИСТИНА для каждого поля обозначает, что ученик посещает данный факультатив, а ЛОЖЬ — не посещает.

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

Основная проблема — научить учеников формальному представлению условий поиска в виде логических выражений. На­пример, от фразы «найти все книги, лежащие выше пятой полки» нужно перейти к логическому выражению: ПОЛКА > 5; или условие «выбрать всех неуспевающих по физике» представить в виде: ФИЗИКА

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 8908 — | 7222 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно