Что называется логической формулой

ЛОГИЧЕСКАЯ ФОРМУЛА

Смотреть что такое «ЛОГИЧЕСКАЯ ФОРМУЛА» в других словарях:

ЛОГИЧЕСКАЯ СЕМАНТИКА — раздел металогики, в к ром изучаются интерпретации логических исчислений. Осн. понятия Л. с. можно разделить на 2 группы: (1) понятия, применение к рых к выражениям логич. исчисления существенно зависит от выбора интерпретации (см. также Модель)… … Философская энциклопедия

ЛОГИЧЕСКАЯ ИСТИННОСТЬ — (в формальной логике) – истинность предложения (суждения, высказывания), обусловленная его формально логич. структурой и принятыми при его рассмотрении законами логики (в отличие от т.н. фактической истинности, для установления к рой необходим… … Философская энциклопедия

ЛОГИЧЕСКАЯ АКСИОМА — формула логико математич. языка, принимаемая в качестве аксиомы при построении формальной теории, истинная в любой структуре для данного языка в силу смысла логич. символов. Л. а. выбираются таким образом, чтобы множество логических следствий из… … Математическая энциклопедия

Логическая дизъюнкция — Дизъюнкция логическая операция, по своему применению максимально приближенная к союзу «или» в смысле «или то, или это, или оба сразу». Синонимы: логическое «ИЛИ», включающее «ИЛИ», логическое сложение, иногда просто «ИЛИ». Это бинарная инфиксная … Википедия

Логическая сумма — Дизъюнкция логическая операция, по своему применению максимально приближенная к союзу «или» в смысле «или то, или это, или оба сразу». Синонимы: логическое «ИЛИ», включающее «ИЛИ», логическое сложение, иногда просто «ИЛИ». Это бинарная инфиксная … Википедия

семантика логическая — СЕМАНТИКА ЛОГИЧЕСКАЯ раздел логической науки, в котором изучают отношения выражений языка к обозначаемым объектам и выражаемому содержанию. Если семантика как раздел семиотики имеет дело с общими аспектами интерпретации любого типа… … Энциклопедия эпистемологии и философии науки

форма логическая — ФОРМА ЛОГИЧЕСКАЯ способ связи составных частей содержания мысли в отличие от самого этого содержания, результат отвлечения от «материи» мысли, т.е. от того, какие именно индивиды, свойства, отношения, классы, ситуации и т.п. являются… … Энциклопедия эпистемологии и философии науки

Алгебра кортежей — Алгебра кортежей математическая система моделирования и анализа многоместных отношений. Содержание 1 Использование термина 2 Определение 3 На чем … Википедия

Источник

5.2. Что такое логическая формула?

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

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

В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул.

В качестве примера рассмотрим высказывание «если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог«. Это высказывание формализуется в виде (A v B) ® C; такая же формула соответствует высказыванию «если Игорь знает английский или японский язык, то он получит место переводчика».

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

В качестве другого примера рассмотрим формулу А •, которой соответствует, например, высказывание «Катя самая высокая девочка в классе, и в классе есть девочки выше Кати«. Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями . Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.

Если две формулы А и В «одновременно», то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными .

Равносильность двух формул алгебры логики обозначается символом «=» или символом «є». Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

Источник

Конспект на тему » Что такое логическая формула?»

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

2. Что такое логическая формула?

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

Всякая логическая переменная и символы «истина» («1») и «ложь» («0») — формулы.

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

В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул.

В качестве примера рассмотрим высказывание «если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог». Это высказывание формализуется в виде (A v B) C. Такая же формула соответствует высказыванию «если Игорь знает английский или японский язык, то он получит место переводчика».

Как показывает анализ формулы (A v B) C, при определённых сочетаниях значений переменных A, B и C она принимает значение «истина», а при некоторых других сочетаниях — значение «ложь» (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми.

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

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

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

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

Источник

Логические выражения

Понятие логического выражения или логической формулы вводится индуктивно.

Логической формулой является

1) любая логическая переменная (переменная, принимающая одно из двух значений: истина или ложь, обозначаемых далее 1 и 0 соответственно), а также каждая из двух логических констант (постоянных) — 0 и 1, является формулой;

Формулой является, например, следующее выражение (x & y) z. Каждой формуле при заданных значениях входящих в нее переменных можно приписать одно из двух значений — 0 или 1.

Формулы А и В, зависящие от одного и того же списка переменных x1, x2, x3, …, xn, называют равносильными, или эквивалентными, если на любом наборе значений переменных x1, x2, x3, …, xn они принимают одинаковые значения. Для обозначения равносильности формул используется знак равенства, например, А = В.

Любую формулу можно преобразовать к равносильной ей, в которой используются только операции &, и отрицание.

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

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

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

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

· отрицание — первый, наивысший приоритет;

· конъюнкция — второй приоритет;

· дизъюнкция, разделительная дизъюнкция — третий приоритет;

· импликация, эквивалентность — низший приоритет.

Изменить порядок выполнения операций можно с помощью расстановки скобок.

В алгебре логики дизъюнкция (логическое сложение) играет роль, аналогичную сложению в алгебре действительных чисел, конъюнкция (логическое умножение) — умножению, а отрицание (инверсия значения логической формулы) — унарному минусу (инверсия знака обычной формулы). Операция эквивалентность аналогична операции отношения “=”, а операция импликация — операции отношения “ ”.

Канонические формы

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

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

Формулу называют элементарной конъюнкцией, если она является конъюнкцией одной или нескольких переменных, взятых с отрицанием или без отрицания. Например, формулы x₂, x₂, x₁ & x₃, x₁ & x₃ & x₁ & x₃ являются элементарными конъюнкциями.

Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций. ДНФ записываются в виде A₁ A₂ … A_n, где каждое A_i — элементарная конъюнкция. Например, x₂ x₁ & x₃, x₂ & x₂ x₁ & x₂— дизъюнктивные нормальные формы.

Формула А от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если

1) А является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных x₁, x₂, …, x_k, причем на i-м месте этой конъюнкции стоит либо переменная x_i, либо ее отрицание;

2) все элементарные конъюнкции в такой ДНФ попарно различны.

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

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

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

Теорема. Пусть — f (x₁, x₂, …, x_n)булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию f, которую можно построить по следующему алгоритму:

1. В таблице истинности отмечаем наборы переменных, на которых значение функции f равно единице.

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

3. Все полученные конъюнкции связываем операциями дизъюнкции.

Доказательство. Каждая элементарная конъюнкция, вошедшая в СДНФ, принимает значение 1 только на единственном наборе. Отсюда следует, что если функция на каком-то наборе равна 1, то и вся СДНФ равна 1 в силу того, что по построению соответствующая элементарная конъюнкция, вошедшая в СДНФ, равна 1. А если функция равна 0, то и СДНФ равна 0, т.к. на этом наборе равны 0 все вошедшие в СДНФ элементарные конъюнкции. Таким образом, СДНФ равносильна исходной функции.

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

Доказательство. Для всех функций, отличных от 0, это можно сделать с помощью СДНФ, а ноль можно выразить, например, как x &`x.

Методические рекомендации

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

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

2) Во многих языках программирования используется только несколько логических операций, как правило, операция логического сложения, логического умножения и отрицания, а также операция разделительной дизъюнкции. Поэтому, если полученная формула содержит не только операции &, и отрицание, то учащиеся должны уметь выполнять тождественные преобразования для построения ДНФ (дизъюнктивной нормальной формы). Умение выполнять тождественные преобразования основано на знании основных законов алгебры логики, но формируется это умение в результате выполнения большого числа заданий. На формирование этого умения времени практически не отводится, но практика показывает, что достаточно научить учащихся выражать операции импликации и эквивалентности через &, и отрицание. Большинство законов алгебры логики ученикам интуитивно понятны и не требуют запоминания. Исключение составляют законы поглощения и де Моргана. Последние особенно часто применяются в программировании. Знакомство с законами алгебры логики начинается в базовом курсе информатики и продолжается в старшей школе.

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

4) Перед изложением формулировки теоремы о СДНФ надо пояснить, для чего используются нормальные формы (поиск аналитического вида булевой функции, заданной таблицей истинности; минимизация представления булевой функции с использованием только трех логических операций &, и отрицания: такая задача возникает при конструировании микросхем, в частности, для производства компьютеров, и т.д.). Учащимся на примерах надо показать, что проблема представления формул в виде СДНФ не надуманна, ее решение имеет важное практическое значение в информатике. Данная тема подлежит рассмотрению в старших профильных классах.

5) Если вы задаете своим ученикам задания на построение отрицания к сложному высказыванию (а проще всего это делать через построение отрицания к соответствующему логическому выражению), то им следует пояснить, почему в этом случае квантор общности заменяется на квантор существования и наоборот (см. “Логические операции. Кванторы”).

Очевидно, что высказывание, содержащее квантор общности (например, “Все мужчины старше 70 лет имеют длинную седую бороду”), можно заменить на следующее: “И Иванов А.П., и Кравцов И.Г., и Петухов С.П., и … старше 70 лет и имеют длинную седую бороду”. Это высказывание можно записать следующей формулой: И & К & П & …, где буквой И обозначено высказывание “Иванов А.П. (который старше 70 лет) носит длинную седую бороду”, буквой К обозначено высказывание “Кравцов И.Г. носит длинную седую бороду” и т.д. При построении отрицания к первоначальному сложному высказыванию, содержащему квантор общности, воспользуемся законом де Моргана. Тогда получим:

6 От латинских слов idem — тот же самый и potens — сильный; дословно — равносильный.

Источник

Основы алгебры логики

Логические формулы и таблицы истинности

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

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

Будем обозначать логические переменные латинскими буквами. Каждая переменная может принимать только два значения: истина или ложь (0 или 1).

Определение. Логической формулой является:
1) любая логическая переменная или логическая константа;
2) если А и B – логические формулы, то и А * B – тоже являются логическими формулами, где * – любая бинарная логическая операция.

Использование таблиц истинности для доказательства тождеств и тавтологий

Определение. Две формулы – А и B, зависящие от одного и того же набора переменных, называются равносильными или тождественными, если на любом наборе значений переменных они имеют одинаковые значения. Обозначают равносильные формулы знаком равенства: А = B.

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

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

Источник