<<
>>

6.5. Сокращенный метод проверки (метод нуля и единицы).

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

1.

Чтобы сокращенно проверять формулу, необходимо прежде всего хорошо помнить таблицы для логических союзов. Эти таблицы можно выписать по аналогии с мате-матическими формулами в следующем виде: (не 1) = 0, (1 или 0) = 1, (0 или 0) = 0, (1 и 0) = 0, (0 и 0) = 0, (1 - 0) = 0, (0 0) = 1, (1=0) = 0, (0 = 0) = 1.

а. (не 0) = 1,

б. (1 или 1) = 1, (0 или 1) = 1,

(і)

в. (1 и 1) = 1, (0 и 1) = 0,

г. (1->1) = 1, (0 1) = 1,

Д. (1 = 1) = 1, (0sl) = 0, Сравните эти способы записи с таблицами для отдельных союзов.

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

Проверяя формулу сокращенным образом, мы обходим тот пункт рассуждения, в котором происходит подстановка в формулу вместо переменных р, q, г,... произвольных предложений Р, (?, Я, ... Здесь просто мы переменные р, q, г,... представляем как конкретные предложения, которые могут быть истинными или ложными, и поэтому вся формула, например,

(р q) ("* Р)Ь

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

(P-+Q)-* [(не (?) {не Р)].

Если мы считаем переменные р, q, г,..., входящие в формулу, предложениями, то для каждой из них является истиной, что р = 1 или р = 0, q = 1 или q = 0, г = 1 или г = 0, ... Поэтому мы должны, как и в несокращенном методе, рассмотреть множество различных возможностей. Но мы можем эти возможности записать также аналогично математическим выражениям, подобно тому как мы записали таблицы. Например, рассматривая (исследуя) формулу (Р q) [і46 q) {не р)Ь мы можем получающиеся здесь возможности записать следующим образом:

(1 1) [{не і) ^ {не 1)ь (1 0) [{не 0) {не 1)], (0-> 1) [{не 1) {не 0)], (0-+0)-*[{не 0) (не 0)].

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

Поэтому мы при помощи наших таблиц вычислим значения приведенных выражений и получим:

{(1 [(не 1) (не 1)]} - [(1 (0-> 0)] =

- (1 1) = 1, {(1 [(не 0) (не 1)] } - [(1 0) (1 0)] -

- (0 0) = 1, {(О-М)-* [(не 1)-+{не 0)]} - [(0^1)^(0-^1)] =

= (1 -М) = 1,

{(О 0) [(не 0) (не 0)]} = [(0 0) (1 1)] =

= (1 1) = 1.

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

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

(р -> не q) (q ->¦ не р).

Для этого сразу выпишем подстановки в нее и сразу же вычислим их.

[(1 не 1) (1 не 1)] = [(1 0) (1 0)] =

= (0^0) - 1,

[(1 не 0) (0 не 1)] = [(1 1) (0 0)] =

= (1 1) = 1,

[(0 не 1) ->- (1 не 0)] = [(0 0) (1 1)] =

= (1->1) = 1,

[(0 не 0) (0 не 0)] = [(0 1) (0 1)] =

= (1 1) = 1.

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

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

[(нер) ->- q] [(не q)->p].

Ход мысли будет следующим:

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

ее значение должно быть равным нулю.

Поскольку наша формула является импликацией, то она может оказаться ложным предложением только тогда, когда при некоторой подстановке условие этой формулы окажется истинным, а ее заключение — ложным, т. е. тогда, когда (не р) q будет равно 1 и одновременно когда (не q) -»¦ р будет равно нулю.

Чтобы заключение (не q) р было равно нулю, необходимо, чтобы в последнем предложении условие было истинным, а заключение — ложным, т. е. чтобы (не q) = 1, а р = 0. Только тогда [(не q) р] = 0.

Поэтому эта формула может быть ложной только тогда, когда/? = Оид = 0, а поэтому достаточно испытать, истинна ли эта формула именно в этом случае.

Поэтому мы испытаем только посылку (условие) всей формулы, т. е. предложение (не р) q, является ли оно истинным или же ложным при такой подстановке, так как о заключении всей формулы, т. е. о предложении (не q) ->- р, нам известно, что оно при этой подстановке является ложным, ибо именно эту-то подстановку мы искали. Но когда р = 0 и q = 0, тогда (не р) — 1, поэтому \(не р) q] = 0, т. е. при той единственной подстановке, которая обращает в нуль заключение формулы, условие (посылка) также равно нулю и, следовательно, вся наша формула истинна. А поскольку формула оказалась истинной при той единственной подстановке, при которой она могла бы быть ложной, то вся формула истинна всегда, т. е. эта формула является теоремой логики.

Все это рассуждение можно автоматизировать и проводить механически. Например, испытаем еще следующую формулу:

(Р Я) 1(Я г) (р -> г)].

Итак, чтобы значение всей этой формулы было равно нулю, должно быть (р q) == 1 и [(q г) (р г)] == - 0. Но чтобы l(q CP г)] = о, должно быть

. (q п = 1 и (р Г) = о. А чтобы было (р г) = О необходимо, чтобы было р = 1 и г = О, и поэтому только при этой подстановке формула может оказаться ложной, т. е. ее значение может оказаться равным нулю Поищем еще условия для предложения q. Поскольку q г должно иметь значение 1, а значение г = 0, то q также должно быть равно нулю, в противном случае q-*r не может равняться 1.

Следовательно, только случай, когда р = 1, q=0 и г=0, может быть тем, при котором значение формулы равно нулю. Но при р = 1 и q = 0 будет (р q) = 0. Итак, хотя в этом единственном случае [(q г) ->> (р ->> г)] =0, так как именно это мы и искали, но в таком случае также и (р q) = 0, а поэтому вся формула истинна для того единственного случая, когда она могла бы быть ложной. Итак, формула является теоремой логики. Заметим, что если бы мы захотели испытать формулу несокращенным методом, то нам потребовалось бы вычислить значение формулы для восьми случаев.

Испытаем еще формулу:

[р (q или г)] ->¦ [(q и г)

Чтобы «она равнялась нулю» (т. е. чтобы ее значение было равно нулю), достаточно, чтобы [р (q или г)] = 1 и [(д и г) —> р] = 0. Чтобы [(q и г) р] = 0, должно быть (q и г) = 1 и р = 0. А чтобы (q и г) = 1, должно быть q = 1 и г = 1. Исследуем условие: (q или г) = 1 и р = 0, в этом случае [р (q или г) ] — 1. Условие истинно, а заключение ложно, что мы и искали, и формула для этого случая оказалась ложной, а раз она может быть ложной, то она не является теоремой логики. Если бы мы испытывали формулу несокращенным методом, то мы непроизводительно могли бы рассмотреть даже семь остальных подстановок, прежде чем напасть на рассмотренную нами подстановку, при которой формула только и оказывается ложной. Рассуждая же сокращенным методом, мы сразу же нашли нужную нам подстановку (решающую весь вопрос отрицательно)1).

Рассуждения, в точности совпадающие с приведенными здесь, проводятся с помощью так называемых семантических таблиц Бета. Эти таблицы дают простой и удобный прием проверки того, является ли данная формула теоремой логики или нет. (Прим. ред.) УПРАЖНЕНИЯ

Проверьте, являются ли теоремами логики следующие формулы с одной переменной:

р = (г»е р), (не р)—*рч /> == р, (р или р) —» р} не {р и[р = (не />)]}, />-*р, Р==[(не р)^(р и />)], р или [р = (не /?)], не [р-*(нер)]і не [р — (не />)], (р или р) —* (р и р).

Проверьте несокращенным методом следующие формулы:

(Р—Я)-*Цне р) или q], (p-»q)EE[p = (p и q)], (P Я) — (Я — Р), (Р = Я) — (р я).

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

[(не р)-*я]-*[(пе ?)->/>], [(p-»q) и (не q))->He pt [(р и q) или Я]-*(Р и 1(р-*Я) и (г-»?)]-*[(Р и

{[(г Я) (Я и г)-» р]}.

<< | >>
Источник: А. ГЖЕГОРЧИК. ПОПУЛЯРНАЯ ЛОГИКА. ОБЩЕДОСТУПНЫЙ ОЧЕРК ЛОГИКИ ПРЕДЛОЖЕНИЙ. ИЗДАНИЕ ТРЕТЬЕ, СТЕРЕОТИПНОЕ. МОСКВА «НАУКА», 517с. 1979

Еще по теме 6.5. Сокращенный метод проверки (метод нуля и единицы).:

  1. 6.5. Сокращенный метод проверки (метод нуля и единицы).
  2. Возрождение римского права. Глоссаторы
  3. Онегин и Ленский.
  4. МЕТОД АКТИВНОГО ПОВТОРЕНИЯ
  5. Кто за рулем?
  6. ИССЛЕДОВАНИЯ
  7. 6. Мозг и его элементы — нейроны
  8. НЕКОТОРЫЕ ФИЗИОЛОГИЧЕСКИЕ КОНСТАНТЫ ОРГАНИЗМА ЧЕЛОВЕКА, ОСНОВНЫЕ И ПРОИЗВОДНЫЕ ВЕЛИЧИНЫ И ЕДИНИЦЫ СИ
  9. Оценка сократительной функции матки
  10. 5. Краткий обзор других методов диагностики заболеваний органов пищеварения
  11. СПИСОК СОКРАЩЕНИЙ