Основы математической логики

Одним из фундаментальных понятий математической логики является понятие высказывания.

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

ПРИМЕРЫ Высказываниями являются следующие предложения:

• 1). «Волга впадает в Каспийское море» .
• 2). «Москва стоит на берегу Невы» .

Первое высказывание — истинно, а второе — ложно.

Предложения:

• 1). «х + у = 4» .
• 2). «Город стоит на берегу реки» высказываниями не являются ввиду их недостаточного уточнения.

В логике высказываний интересуются не содержанием, а истинностью или ложностью высказываний. Истинностные значения — истина и ложь — будем обозначать буквами И и Л соответственно. Множество {И, Л} называется множеством истинностных значений.

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

Рассмотрим логические операции над высказываниями, при которых истинностные значения составных высказываний определяются только истинностными значениями составляющих высказываний, а не их смыслом. Эти логические операции являются операциями отрицания, конъюнкции и дизъюнкции.

Отрицанием высказывания Р называется высказывание P истинное, когда высказывание Р ложно, и ложное, когда высказывание Р является истинным. Отрицание Р обозначается через «P «и читается как «не Р «. Отрицание соответствует частице «не» .

Конъюнкцией двух высказываний Р и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания. Конъюнкция высказываний Р и Q обозначается через «P x Q» и читается как «Р и Q». Конъюнкции соответствует соединение высказываний союзом «и» .

Дизъюнкцией двух высказываний Р и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны. Дизъюнкция этих высказываний обозначатся «PVQ и читается как «Р или Q». Дизъюнкция соответствует соединению высказываний союзом «или» .

Импликацией двух высказываний Р и Q называется высказывание, ложное тогда и только тогда, когда Р истинно, а Q ложно. Импликация высказываний P и Q обозначается «P^Q» и читается как «из P следует Q».

Эквивалентностью (эквиваленцией) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинностные значения Р и Q совпадают.

Эквиваленция высказываний Р и Q обозначается «Р ~ Q» и читается как «Р эквивалентно Q».

ПРИМЕР 1.

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

Решение Составное высказывание состоит из следующих простых:

А — «Допоздна работаешь на компьютере».

В — «Утром просыпаешься поздно».

С — «Утром встаешь с головной болью».

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

А^(В х С).

ПРИМЕР 2.

Представить логической формулой высказывание:

«Если фирма заботится о качестве товаров или об ассортименте, то это приведет к росту объема сбыта продукции и повышению прибыли от ее реализации».

Решение Составное высказывание состоит из следующих простых:

Х — «Фирма заботится о качестве товаров».

Y — «Фирма заботится об ассортименте».

Z — «Рост объема сбыта продукции».

U — «Повышение прибыли от реализации продукции».

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

(X V Y) ^ (Z х U).

ПРИМЕР 3.

Для логической формулы: (A х B)—(C х D) разработать составное высказывание относительно мероприятий по повышению эффективности работы фирмы.

Решение Представим простые высказывания:

A — «Фирма терпит убытки».

В — «Фирма снижает объемы реализации продукции».

С — «Фирма должна снизить издержки производства».

D — «Фирма должна реализовать программу продвижения продукии на рынок».

С учетом (A х B)——(С х D) получаем следующее составное высказывание:

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

ЗАДАНИЕ Записать сложные высказывания в виде логических формул:

• 1).Если потребитель отдает предпочтение качеству товара и его упаковке, то фирма должна улучшить качество своей продукции или заняться улучшением его дизайна.
• 2).Если выпуск нового продукта обеспечит высокий доход, расширение фирмы и привлечение новых инвестиций, фирме необходимо приобрести патент на право его выпуска, взять займ или кредит.
• 3). Резкий рост или резкое снижение мировых цен на нефть приводят к резким колебаниям акций топливоэнергетических компаний и фирм-потребителей нефтепродуктов.

Разработать составные высказывания:

• 4). Для логической формулы: (AVB)^(C x D) разработать составное высказывание относительно карьеры молодого специалиста на фирме.
• 5). Для логической формулы: (AxB)^(C V D) ~ К разработать составное высказывание относительно успеш ной подготовке студента к сессии и переходу его на следующий курс.

Основные понятия алгебры Буля Всякое высказывание, построенное с помощью операций (V, x, ^-), имеет некоторое истинностное значение, зависящее от значений соответствующих высказываний. Любое высказывание f может быть задано в виде таблицы истинности. Если значение высказывания f зависит от n составляющих высказываний x_i, x₂,.x_n, то таблица истинности содержит 2ⁿ строк. Каждое высказывание x_i называется переменной x_t. При этом сложное высказывание рассматривается как функция f от n переменных. Если придать значению Л численное соответствие «0», а значению И соответствие «1», то функцию n переменных f будем называть булевой функцией f (x₁, x₂,…x_n) от n переменных.

Операции (V,&,^-) образуют сигнатуру алгебры Буля ^- >.

Носитель М алгебры Буля состоит из элементов 0 и 1.

ПРИМЕР Рассмотрим решение, принимаемое 3-мя членами комитета, полагая, что решение будет принято, если большинство членов комитета проголосует «за». Если же большинство членов проголосует «против», решение будет отвергнуто.

Результаты голосования характеризуются таблицей истинности.

ЗАДАНИЕ Товар характеризуется 4-мя свойствами: х₁, х₂, х₃, х₄. Если свойство х_i превосходит аналогичное свойство других товаров или равно ему по своим характеристикам, то его значение принимается равным «1», если его характеристики ниже характеристик свойств других товаров, то принимаем его равным «0» .

Если, по крайней мере, 3 свойства товара превосходят по своим характеристикам свойства других товаров, то он найдет спрос на рынке.

Построить булеву функцию А (х_ьх₂, х₃, х₄) спроса товара на рынке.