Спирина, М.С. Дискретная математика

4.3.1. Операции над сложными высказываниями В русском языке сложные предложения получают из двух дру­ гих с помощью союзов и, а, ест... то, либо, или, тогда и только тогда, когда и др. Назовем такие и аналогичные им союзы логиче­ скими связками. Новые предложения появляются также с упот­ реблением частицы не или слов неверно, что. Эти слова также бу­ дем называть логическими связками. Тогда утвердительные предложения, не содержащие содержащие логиче­ ские связки, называют элементарными составными высказываниями. Напри­ мер, предложение «Все программисты имеют высшее или сред­ нее специальное образование» состоит из двух элементарных пред­ лож ений : «Все программисты имею т высш ее сп еци ал ьн о е образование» и «Все программисты имеют среднее специальное образование». Соединены предложения связкой или. Предложение «Если программист не имеет специального обра­ зования, то он не будет конкурентоспособен на рынке труда» со ­ стоит из простых предложений, соединенных связками если... то и отрицаниями не. Однако не всегда грамматическая форма предло­ жений, в которых выражено суждение, совпадает с его логической формой. Так, сложное суждение может быть представлено простым предложением. Например: «Дискретная математика включает раз­ делы: «Элементы теории множеств», «Элементы теории графов», «Элементы классической и математической логики», «Элементы теории автоматов». Это сложное суждение хотя и представлено про­ стым предложением, но содержит пять простых суждений. Поскольку языком алгебры логики служат булевы функции, то естественно смысловым связкам поставить в соответствие опера­ ции над булевыми переменными. Если простое высказывание является истинным, то ему соот­ ветствует значение логической переменной 1. Если простое вы­ сказывание является ложным, то ему соответствует значение ло ­ гической переменной 0. Если выполняется все (составное) вы­ сказывание, то оно называется истинным и ему соответствует 1 , если не выполняется, то высказывание считается ложным и ему соответствует 0. Составное (сложное) высказывание можно рас­ сматривать как булеву функцию, где аргументами являются се­ мантические характеристики простых высказываний, входящих в сложное, а значением будет семантическая характеристика всего высказывания. Остается только установить соответствие между син­ тактическими связками русского языка и булевыми операциями. Для того чтобы определить, истинно или ложно некоторое сложное высказывание, используют таблицы истинности, в ко­ торых латинскими буквами обозначаются сами высказывания, а 141