Примеры 1

Логические высказывания и функции. Таблицы истинности

БУЛЕВА ЛОГИКА

Двоичные (булевы) векторы

Двоичным (булевым) n-мерным вектором называют набор из n чисел (b ₁, b ₂,..., b_n), каждое из которых может принимать только значения в двоичной системе счисления – 0 или 1.

Двоичный вектор `b<sup>n*</sup> является обратным (инвертирован­ным) к `bⁿ, если он образован из `b<sup>n</sup> заменой нулей единицами, а единиц – нулями. Например, если ` b =(0, 1, 1, 1, 0, 1), то `b^* =(1, 0, 0, 0, 1, 0).

Если в записи двоичного вектора `b<sup>n</sup> длины n устранить запятые, его можно рассматривать как двоичную запись некоторого целого числа. Наименьшим таким числом является 0. Ему соответствует вектор `bⁿ =(0,..., 0). Наибольшим является число 2 ⁿ– 1, которому соответствует `b<sup>n</sup>= (1,..., 1). Следовательно, при помощи полного набора двоичных векторов `bⁿ длины n можно записать все 2 ⁿ целых чисел из интервала [0, 2 ⁿ –1]. Такие числа называют порядковыми номерами векторов. Их используют как в двоичном виде, так и в десятичной системе счисления.

Пример 1. Найти порядковый номер булева вектора `b = (1,0, 0, 1, 0, 1) в десятичной системе счисления.

Решение. Устраняя запятые в векторе, получим двоичную запись 100101. Переводя ее по правилу 2.1.1 в десятичную систему, получим:

100101₂=1×2⁵+1×2²+1×2⁰=32₁₀+4₁₀+1₁₀=37₁₀.

Ответ: десятичный порядковый номер вектора (1,0, 0, 1, 0, 1) равен 37.

Лексикографическим называют такой порядок двоичных век­торов `bⁿ, когда соответствующие им порядковые номера расположе­ны по возрастанию от 0 до 2 ⁿ –1. В качестве примера рассмотрим полное множество 3-мерных булевых векторов, расположенных в лексикографическом порядке:

0 (0, 0, 0), 4 (1, 0, 0),

1 (0, 0, 1), 5 (1, 0, 1),

2 (0, 1, 0), 6 (1, 1, 0),

3 (0, 1, 1), 7 (1, 1, 1).

Пример 2. Упорядочить по возрастанию порядковых номеров булевы векторы длины 6: (1, 0, 1, 0, 1, 1, 0), (0, 1, 1, 0, 1, 0, 0), (0, 0, 1, 1, 0, 1, 0).

Решение. Определяя, как в примере 1, десятичные порядковые номера наборов, получим для них:

(1, 0, 1, 0, 1, 1, 0)↔1010110₂ = 86₁₀, (0, 1, 1, 0, 1, 0, 0)↔110100₂ = 52₁₀, (0, 0, 1, 1, 0, 1, 0)↔11010₂ = 26₁₀.

Искомый порядок получим, располагая векторы в порядке возрастания их номеров: (0,0,1,1,0,1,0), (0,1,1,0,1,0,0),(1,0,1,0,1,1,0).

Практические задания.

1. Найти порядковый номер двоичного вектора (0, 0, 1, 0, 1, 1, 0) в десятичной системе счисления.

2. Упорядочить по убыванию порядковых номеров двоичные векторы длины 5:

(0, 1, 0, 1, 0), (1, 1, 0, 1, 0), (1, 0, 0, 1, 0), (0, 0, 1, 1, 0).

Логика как наука о формах и законах мышления возникла в Древней Греции. Вначале она была составной частью риторики – науки убеждения. Новый импульс развитие логики получило в ХVIII–ХIХ веках, когда в результате развития естественных наук выявилось сходство применяемых в них методов рассуждений. Однако широкое использование математических методов началось только в середине ХIХ века после применения в логике шотландским математиком Дж. Булем математических обозначений.

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

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

Истину обозначают И, ложь – через Л (англ.- Т (true), F (false)). При математическом обозначении И заменяют на 1, Л – на 0.

Простое высказывание выражает одну законченную мысль. Если высказывание всегда истинно (равно 1), либо всегда ложно (0), то его называют константой. Логические константы обычно обозначают маленькими или большими начальными латинскими буквами, при которых также используют нижние индексы. Например: a, b, c, A, B, b ₁, c ₂, A ₂.

Если высказывание может принимать оба логических значения (и 0, и 1), то его называют переменным (логической переменной). Логические переменные обозначают средними латинскими буквами (с индексами и без них), например: x, у, z, Х, Y, Z. x ₁, z ₂, Y ₃.

1) а =«99― самое большое натуральное число» ― высказывание - булева константа, а º0 (Л),

2) b ₁=«99 - самое большое 2- значное натуральное число» ― булева константа, b ₁º1 (И),

3) х =«треугольник является прямоугольным»― булева переменная, поскольку х может принимать значения и 0 и 1,

4) «дом большой» ― фраза не является высказыванием, поскольку выражает субъективное мнение и не ясно, какой дом можно считать большим.

Наряду с фразами на естественном языке, логические константы и переменные могут быть заданы арифметическими условными выражениями, зависящими от числовых вещественных констант и переменных. Например, (x ²+ y ² < 0), (x < y), (x ²+ y ²³10) и другие. Рассмотрим их истинность.

Условие (x ²+ y ² < 0) является логической константой-ложью, по­скольку при всех вещественных x и y оно не выполняется.

При (x= 1, y= 2) условие (x < y) истинно, поскольку 1<2, а условие (x ²+ y ²³10) ложно, так как 1²+2²=5<10. При (x= 4, y= 2) условие (x < y) ложно, поскольку 4>2, а условие (x ²+ y ²³10) истинно, так как 4²+2²= 20 > 10. Т.е. (x < y) и (x ²+ y ²³10) – логические переменные.

Допустим, задан некоторый набор логических переменных, обозначенных, на­пример, x, у, z. Отображение (правило) f, сопоставляющее каждому возможному набору значений переменных (x, у, z) свое логическое значение (0 или 1), называют логической функцией. Обозначается она как f (х, у, z).

Пример 2. Зададим функцию f, зависящую от двух переменных х, у списком, в котором перечислены все возможные логические значения для на­боров переменных (х, у) и соответствующие им значения f:

(х =0, у =0): f =0; (х =0, у =1): f =1; (х =1, у =0): f =1; (х =1, у =1): f =0.

По числу переменных n логические функции называют одноместными (n =1), двухместными (n =2) и т.д.

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

x	y	f

Дата добавления: 2014-01-20