Часто приходится составлять или проверять таблицы истинности логических выражений? Тогда мы идем к вам!
Давно хотел получить удобную программу для расчета таблиц истинности. Простую, чтобы максимально с клавиатуры и минимально мышью, и прямо на компьютере, без Интернета. Где мне ее взять? Честно говоря, я даже не искал. Давно хотел написать сам, ну просто из любви к искусству.
Цель – таблица истинности по логической формуле, вводящейся максимально просто. Консольного приложения вполне достаточно. Задачи – программа должна состоять из набора максимально простых функций, данные представлены в символьной строке и ни в какие другие типы не трансформируются. Используем Си++.
Сначала нужно разработать условные обозначения. Константы: истина – 1, ложь – 0. Переменные – маленькие английские буквы. Операции: - не, * и, + или, # исключающее или, = эквивалентность, > следование. Ну и круглые скобки. Таким образом, всё будет легко набираться в английской раскладке клавиатуры. Можно предусмотреть вариант, когда пропуск знака операции интерпретируется как конъюнкция.
Основная идея следующая. В строку с переменными подставляется комбинация их значений. Выделяются выражения в скобках, вычисляются их значения и вставляются вместо скобок в исходную строку. Это происходит рекурсивно, пока в строке не останется одна константа.
Базовым действием вычисления значения логической формулы является вычисление выражения с константами без скобок согласно приоритета выполнения логических операций. Это будет самая длинная функция программы.
string logElement(string s) { //return value of elementary log expression without pars
size_t pos = 0;
//execution of invertion
for (pos = s.find("--", 0); !(pos == string::npos); pos = s.find("--", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 2); }
}
for (pos = s.find("-0", 0); !(pos == string::npos); pos = s.find("-0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 2); s.insert(pos, "1"); }
}
for (pos = s.find("-1", 0); !(pos == string::npos); pos = s.find("-1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 2); s.insert(pos, "0"); }
}
//execution of conjunction
for (pos = s.find("*", 0); !(pos == string::npos); pos = s.find("*", 0)) {
for (pos = s.find("0*0", 0); !(pos == string::npos); pos = s.find("0*0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
for (pos = s.find("0*1", 0); !(pos == string::npos); pos = s.find("0*1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
for (pos = s.find("1*0", 0); !(pos == string::npos); pos = s.find("1*0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
for (pos = s.find("1*1", 0); !(pos == string::npos); pos = s.find("1*1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
}
//execution of weak disjunction
for (pos = s.find("+", 0); !(pos == string::npos); pos = s.find("+", 0)) {
for (pos = s.find("0+0", 0); !(pos == string::npos); pos = s.find("0+0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
for (pos = s.find("0+1", 0); !(pos == string::npos); pos = s.find("0+1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
for (pos = s.find("1+0", 0); !(pos == string::npos); pos = s.find("1+0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
for (pos = s.find("1+1", 0); !(pos == string::npos); pos = s.find("1+1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
}
//execution of strong disjunction
for (pos = s.find("#", 0); !(pos == string::npos); pos = s.find("#", 0)) {
for (pos = s.find("0#0", 0); !(pos == string::npos); pos = s.find("0#0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
for (pos = s.find("0#1", 0); !(pos == string::npos); pos = s.find("0#1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
for (pos = s.find("1#0", 0); !(pos == string::npos); pos = s.find("1#0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
for (pos = s.find("1#1", 0); !(pos == string::npos); pos = s.find("1#1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
}
//execution of aequivalention
for (pos = s.find("=", 0); !(pos == string::npos); pos = s.find("=", 0)) {
for (pos = s.find("0=0", 0); !(pos == string::npos); pos = s.find("0=0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
for (pos = s.find("0=1", 0); !(pos == string::npos); pos = s.find("0=1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
for (pos = s.find("1=0", 0); !(pos == string::npos); pos = s.find("1=0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
for (pos = s.find("1=1", 0); !(pos == string::npos); pos = s.find("1=1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
}
//execution of implication
for (pos = s.find(">", 0); !(pos == string::npos); pos = s.find(">", 0)) {
for (pos = s.find("0>0", 0); !(pos == string::npos); pos = s.find("0>0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
for (pos = s.find("0>1", 0); !(pos == string::npos); pos = s.find("0>1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
for (pos = s.find("1>0", 0); !(pos == string::npos); pos = s.find("1>0", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "0"); }
}
for (pos = s.find("1>1", 0); !(pos == string::npos); pos = s.find("1>1", 0)) {
if (!(pos == string::npos)) { s.erase(pos, 3); s.insert(pos, "1"); }
}
}
return s;
}
При вычислении инверсии сначала снимаются двойные отрицания. Потом тупой заменой -1 на 0 и -0 на 1 снимаем все инверсии.
Все остальные операции выполняются в цикле «пока они в строке вообще есть». Это сделано для того, чтобы если в выражении операции идут подряд они вычислялись полностью все. Данный подход может привести к ошибке в случае последовательных импликаций. Но порядок действий в последовательности импликаций стоит в любом случае выделять скобками.
Принцип такой. Если найдено определенное сочетание констант и операции, то оно заменяется в строке на результат согласно таблице истинности. Приоритет выполнения – инверсии, конъюнкции, слабые дизъюнкции, сильные дизъюнкции, эквивалентности, импликации. Кто с таким приоритетом не согласен – ставит скобки.
Функция возвращает исходную строку, в которой хранится константа – результат.
Чтобы из исходной формулы выделить выражение в скобках стоит написать отдельную функцию, которая вернет выражение в самых внешних скобках. Ее действие основано на подсчете открывающихся и закрывающихся скобок. Когда счетчик фиксирует первую открывающуюся скобку, запоминается ее позиция, также запоминается позиция последней закрывающейся скобки. Возвращается подстрока между этими позициями.
string in_pars(string s, size_t* p1, size_t* p2) { //return substring in pars
string r = "";
size_t pos, pars_op = 0, pars_clos = 0;
int ind = 0;
for (pos = 0; pos < s.length(); pos++) {
if (s[pos] == '(') {
ind++;
if (ind == 1) pars_op = pos;
}
if (s[pos] == ')') {
ind--;
if (ind == 0) pars_clos = pos; ;
}
}
for (size_t i = pars_op + 1; i < pars_clos; i++) r += s[i];
*p1 = pars_op; *p2 = pars_clos;
return r;
}
Ну и собственно рекурсивный расчет происходит в функции full_log_calc, которая сначала ищет выражение в скобках в исходной строке.
Если исходная строка не содержит скобок, то вычисляется значение выражения, очищается исходная строка, в нее вставляется результат и возвращается в точку вызова.
Если найдена константа в скобках (это может быть при наборе), то скобки удаляются и рекурсивно вызывается функция full_log_calc, которая снова проверяет, есть ли скобки.
Если найдено выражение в скобках, то выполняется рекурсивная попытка его вычисления, удаляются скобки, и поскольку текущая строка скобок больше не содержит, то можно вернуть результат рекурсивного вызова этой же самой функции.
string full_log_calc(string s) {//full calculation of a logical expression
string r, q;
size_t p1, p2;
r = in_pars(s, &p1, &p2); //cout << s << " in pars " << r << endl;
if (r == ""&& p1 == 0 && p2 == 0) {
s = logElement(s);
return s;
}
if (r.length() == 1) {
s.erase(p1, p2 - p1 + 1); s.insert(p1, r);
return full_log_calc(s);
}
if (!(r == ""&& p1 == 0 && p2 == 0)) {
q = full_log_calc(r);
s.erase(p1, p2 - p1 + 1); s.insert(p1, q);
return full_log_calc(s);
}
}
Возможно, что код где-то избыточен. Оправдываюсь: я делаю рекурсию всего четвертый раз в жизни (первый – факториал, второй – степень, третий – задача на оптимальный путь из ЕГЭ, чтобы увидеть все варианты движения робота по плоскости).
Перед попыткой расчета выражения стоит проверить его на возможные ошибки.
Проверка на непарные скобки. Если возвращается 0, то всё в порядке.
interr_pars(string s) {//error - unpaired brackets
size_t pos;
int count = 0;
for (pos = 0; pos < s.length(); pos++) {
if (s[pos] == '(') count++;
if (s[pos] == ')') count--;
}
returncount;
}
Проверка на недопустимые символы. Использовал множества. Если возвращается 0, то всё в порядке.
interr_simbol(string s) {//error - invalid simbol
int ind = 0;
set <char> valid;
valid.insert('1'); valid.insert('0'); valid.insert('-'); valid.insert('+'); valid.insert('*');
valid.insert('>'); valid.insert('#'); valid.insert('='); valid.insert('('); valid.insert(')');
for (size_t i = 0; i < s.length(); i++) { if (valid.count(s[i]) == 0) { ind++; break; } }
returnind;
}
Проверка на пропущенную константу. Если ошибок нет, то вернет 0.
interr_not_arg(string s) {//error - 2 operation without const between its
int ind = 0;
set <char> valid_op, valid_pars;
valid_op.insert('+'); valid_op.insert('*');
valid_op.insert('>'); valid_op.insert('#'); valid_op.insert('='); valid_pars.insert('('); valid_pars.insert(')');
for (size_t i = 0; i < s.length() - 1; i++) {
if (valid_op.count(s[i]) != 0 && valid_op.count(s[i + 1]) != 0
|| valid_op.count(s[i]) != 0 && s[i + 1] == ')'
|| s[i] == '('&& valid_op.count(s[i + 1]) != 0
)
{
ind++; break;
}
}
returnind;
}
Проверка на пропущенную операцию. Если ошибок нет, то вернет 0. Данная функция избыточна, если отсутствие операции интерпретируется как конъюнкция. В этом случае исключаем ее из списка проверок.
int err_not_op(string s) {// error - 2 args without operation sign
int ind = 0;
set <char> valid_dig;
valid_dig.insert('1'); valid_dig.insert('0');
for (size_t i = 0; i < s.length() - 1; i++) {
if (valid_dig.count(s[i]) != 0 && valid_dig.count(s[i + 1]) != 0
|| valid_dig.count(s[i]) != 0 && s[i + 1] == '('
|| s[i] == ')' && valid_dig.count(s[i + 1]) != 0
|| valid_dig.count(s[i]) != 0 && s[i + 1] == '-'
|| s[i] == ')' && s[i + 1] == '-'
)
{
ind++; break;
}
}
return ind;
}
Проверка на пустые скобки. Если вернет 0, то нет таковых.
int err_pars_empty(string s) {//error - pars is empty
size_t pos;
int count = 0;
for (pos = 0; pos < s.length() - 1; pos++) {
if (s[pos] == '(' && s[pos + 1] == ')') count++;
}
return count;
}
Итак, из приведенных функций уже можно сформировать программу, которая рассчитает логическое выражение с константами. Именно эти функции придется использовать при построении таблицы истинности, когда комбинация значений будет подставлена в логическую формулу с переменными.
Но логическая формула содержит переменные, стало быть, на место переменных нужно подставлять наборы констант, чтобы рассчитать значение формулы. Значит, наборы констант нужно сформировать, а перед этим нужно сформировать список переменных.
Сначала разработаем функцию, которая сформирует строку конкретной логической комбинации значений переменных. Принцип простой. Если мы знаем число переменных в формуле, а мы его непременно узнаем, то двойка в этой степени и будет числом комбинаций. Если переменных три, то комбинаций восемь. Их можно закодировать как двоичные числа от нуля до семи и записать в строке. При этом длина строки должна быть равной числу переменных, а пустые разряды двоичных чисел заполнены нулями. Это и делает функция LogCombin.
string LogCombin(int na, int x) {//form string with combination of logical constant
int ost;
string s = ""; char c;
for (; x > 0; c = '0' + x % 2, s = c + s, x /= 2);
for (; s.length() < na; s = "0" + s);
return s;
}
Она принимает число переменных na и число x меньшее na – текущую комбинацию значений. Первый цикл формирует в строке двоичную запись числа x, второй цикл дополняет нулями пустые разряды.
А теперь еще одна большая функция, которая собственно таблицу истинности и сформирует – функция FormLogTable. Она принимает строку с формулой, а возвращает таблицу истинности. Ее текст дам полностью, а этапы ее работы поясню отдельно.
string FormLogTable(string s) { //form result table
//1 - переменные
int TRUE = 0, FALSE = 0;
string result = ""; //result table
string logparam = "";//list of argument names as string
set <char> lit; set <char> ::iterator it;//list of argument names as set
int NumberArgs, // number of arguments
NumberCombin;// number of combinations of arguments volume
// 2
for (size_t pos = 0; pos < s.length(); pos++) {// form list of argument names as set from formula
if (s[pos] >= 'a' && s[pos] <= 'z') { lit.insert(s[pos]); }
}
for (it = lit.begin(); it != lit.end(); it++) {// form list of argument names as string from set
logparam += *it;
}
result += s + '\n' + logparam + '\n';
//3
NumberArgs = lit.size();//calculate number of arguments
NumberCombin = (int)pow((float)2, (float)NumberArgs);//calculate number of arguments combinations
for (int i = 0; i < NumberCombin; i++) {//perebor kombinatsiy
string f = LogCombin(NumberArgs, i);
string vol = s;//for form constant formula
//4
for (size_t k = 0; k < logparam.length(); k++) {
for (size_t pos = 0; pos < vol.length(); pos++) {
string r = "";
if (s[pos] == logparam[k]) { vol.erase(pos, 1); r += f[k]; vol.insert(pos, r); }
}
}
//5
if (err_simbol(vol) != 0 || err_pars(vol) != 0 //possible errors
|| err_pars_empty(vol) != 0 || err_not_op(vol)
|| err_not_arg(vol) != 0
)
{
return "";
}
//6
if (full_log_calc(vol) == "1") TRUE++;
if (full_log_calc(vol) == "0") FALSE++;
result += f + " " + vol + " " +full_log_calc(vol) + '\n';
}
//7
ostringstream itogi;//to print summas of true end false
itogi << "Истина: " << TRUE << endl << "Ложь: " << FALSE << endl;
result += itogi.str();
return result;
}
На этапе 1 объявляются самые важные переменные: TRUE и FALSE, они сохранят количество истинных и ложных значений формулы, строка result сохранит таблицу истинности, строка logparam хранит список аргументов формулы, множество lit и его итератор it предназначены для формирования списка аргументов, целые NumberArgs и NumberCombin хранят число аргументов и число комбинаций их значений.
На этапе 2, читая формулу в первом цикле, формируется множество английских букв, которые в ней встречаются, то есть множество аргументов формулы. Второй цикл записывает аргументы в строку logparam. И наконец в строку результата работы всей функции записывается исходная формула (почему бы и нет) и с новой строки список ее аргументов в алфавитном порядке.
На этапе 3 выясняется число логических аргументов и число комбинаций их значений и запускается цикл перебора всех комбинаций как простой счет чисел от нуля до NumberCombin-1.
Два вложенных цикла на этапе 4 заменяют буквы в формуле на их логические цифровые значения текущей комбинации.
На этапе 5 происходит проверка на возможные ошибки. Если таковые находятся, то функция завершает свою работу и возвращает пустую строку, ибо далее работать бессмысленно.
На этапе 6 рассчитывается очередная строка таблицы истинности и продолжается формирование чисел итоговых сумм истинных и ложных значений формулы. Здесь заканчивается цикл, открытый на третьем этапе.
На этапе 7 в итоговую строку впечатываются суммы истинных и ложных значений формулы и дается команда на возврат сформированной строки.
И последний штрих. А почему бы при наборе формулы нам не пропустить знак конъюнкции, как мы это обычно делаем при письме от руки? А если мы его пропустим, то перед расчетом его нужно вставить на нужные места. Эту задачу решает функция InsertConjunction.
string InsertConjunction(string s) {//insert sign of conjunction where nessesery
set <char> lit;
for (char c = 'a'; c <= 'z'; c++) {// form list of argument names as set
lit.insert(c);
}
lit.insert('1'); lit.insert('0');
for (size_t i = 0; i < s.length() - 1; ) {
if (lit.count(s[i]) != 0 && lit.count(s[i + 1]) != 0
|| lit.count(s[i]) != 0 && s[i + 1] == '('
|| s[i] == ')' && lit.count(s[i + 1]) != 0
|| lit.count(s[i]) != 0 && s[i + 1] == '-'
|| s[i] == ')' && s[i + 1] == '-'
|| s[i] == ')' && s[i + 1] == '('
)
{
s.insert(i + 1, "*");
}
else i++;
}
return s;
}
Итак, мы имеем полный инструментарий, чтобы написать консольную программу, которая по формуле, введенной с клавиатуры, построит таблицу истинности. Не забудем при этом файлы-заголовки, функции из которых были использованы для построения приведенного выше кода.
#include<iostream>
#include<sstream>
#include<cmath>
#include<string>
#include<set>
using namespace std;
И собственно функция main.
int main() {
setlocale(LC_ALL, "");
string s;
for (;;) {
cout << "ТАБЛИЦЫ ИСТИННОСТИ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ" << endl;
cout << "Допустимые имена переменных – английские буквы от a до z." << endl;
cout << "Допустимые логические константы – 0 (Ложь) и 1 (Истина)." << endl;
cout << "Допустимые обозначения логических операций и приоритет выполнения –" << endl
<< "() скобки," << endl
<< "- инверсия," << endl
<< "* конъюнкция (допустимо отсутствие знака)," << endl
<< "+ слабая дизъюнкция," << endl
<< "# сильная дизъюнкция," << endl
<< "= эквивалентность," << endl
<< "> импликация." << endl
<< endl << "Введите логическое выражение." << endl;
cin >> s;
s = InsertConjunction(s);
cout << FormLogTable(s);
system("pause");
}
return 1;
}
В main устанавливается локаль кодировки, используемой операционной системой, объявляется строка для записи формулы и открывается вечный цикл. Если знаки конъюнкции пропущены, то они устанавливаются на нужные места. В выходной поток сгружается таблица истинности. Системная пауза вызывается для того, чтобы после отработки одного запроса заголовок для следующего сразу не выводился.
Выход из программы осуществляется закрытием окна консоли.
Преимущества данного приложения: простой набор формул, отсутствие необходимости инсталляции. Преимущества самого подхода к реализации: работа с символами, результат хранится в строке, этот набор функций можно использовать и в оконном приложении. И еще немаловажное замечание: этот код можно трансформировать на Java Script или встроить в оконную оболочку ОС Windows. Последнее уже успешно проделано, но это другая история.
Этот код успешно компилировался в Visual Studio 2019, OnlineGDB (www.onlinegdb.com/online_c_compiler, с некоторыми недочетами в кириллице), в C-Free 4.0, C-Free 5.0 и Dew-C++ 5.11 кириллица, набранная под сетевой операционной системой не прошла.
Надеюсь, что учителям информатики это поможет.