Практически важнейшей сферой применения логики предикатов к
логико-математической практике является сфера построения доказательств
различных теорем, основывающаяся на теории логического следования. Более
сложное строение формул логики предикатов, по сравнению с формулами
логики высказываний, дает возможность проводить более сложные
доказательства и в результате получать более тонкие заключения. [1]. Смотри таже
2. Техника исчисления базисных предикатов по Е.А. Мирончик 2017 и ЕГЭ Задача 18 ( поразрядная конъюнкция )
3. Shooting problems P-22,P-23,P-25 via "Calculus of basic predicates" by E.A.Mironchick 2017
Всюду в дальнейшем N+ означает множество неотрицательных
целых чисел.По умолчанию х всегда принадлежит N+
Определим предикаты
A(x) = { 1; x ∈ [70;90] ;
0; x !∈ [70;90]
}
B(x) = { 1; x ∈ [40;60] ;
0; x !∈ [40;60]
}
C(x) = { 1; x ∈ [0;N] ;
0; x !∈ [0;N]
}
F(x) = (¬A(x)=>B(x))^(¬C(x)=>A(x))
При каком наименьшем N область истинности F(x) содержит более 30 целых чисел
∀ x: (¬A(x)=>B(x))^(¬C(x)=>A(x)) <=> (A(x)vB(x))^(C(x)vA(x))
∀ x: (A(x)vB(x))^(C(x)vA(x)) <=> A(x)vB(x)^C(x)
Область истинности А(х) содержит 21 целое число.
Область истинности В(х)^C(x) есть [40;60]∩[0;N] и должна содержать не менее 11 целых чисел
Если N ∈ [40;60] то [40;60]∩[0;N]=[40;N]
При N-40+1 = 10 => N=49 ∈[40;60] область истинности
F(x) = A(x)vB(x)^C(x) содержит 31 целое число так как является объединением областей истинности А(х) и В(х)^C(x)
Следующие примеры из работы
К.Ю. Поляков Множества и логика в задачах ЕГЭ 2015
Ниже следуют решения задач №3,5,6 использующие алгебру предикатов :-
A(x) = { 1; x ∈ [x1;x2];
0; x !∈ [x1;x2]
}
P(x) = { 1; x ∈ [37;60] ;
0; x !∈ [37;60]
}
Q(x) = { 1; x ∈ [40;77] ;
0; x !∈ [40;77]
}
F(x) = P(x) => ((Q(x)^¬A(x)) => ¬P(x) ;
Определить наименьшую длину области истинности А(х)
∀ x: F(x)= P(x) => ((Q(x)^¬A(x)) => ¬P(x) = True
P(x) => ((Q(x)^¬A(x)) => ¬P(x) <=> ¬P(x)v¬Q(x)vA(x)v¬P(x)
P(x) => ((Q(x)^¬A(x)) => ¬P(x) <=> ¬P(x)v¬Q(x)vA(x)
∀ x : ¬P(x)v¬Q(x)vA(x) = 1
∀ x : ¬(¬P(x)v¬Q(x))=>A(x) = 1
∀ x : P(x)^Q(x) => A(x) = 1 (*)
Допустим
∃ y : (P(y)^Q(y) = 1) ^(A(y) = 0) = 1
Тогда
∃ y : P(y)^Q(y) => A(y) = 0
мы получаем противоречие с (*)
Таким образом, наименьшая область истинности A(x) есть пересение областей истинности P(x) и Q(x) , то есть [37;60]∩[40;77]=[40;60]
P(x) = { 1; x ∈ [2,4,6,8,10,12] ;
0; x!∈ [2,4,6,8,10,12]
}
Q(x) = { 1; x ∈ [4,8,12,116] ;
0; x!∈ [4,8,12,116]
}
Определить область истинности предиката А(х),
как множество натуральных чисел таким образом,что
∀ x: P(x) => ((Q(x)^¬A(x)) => ¬P(x)) = 1
∀ x: ((Q(x)^¬A(x)) => ¬P(x)) <=> (¬Q(x)vA(x)v¬P(x))
∀ x: ¬P(x)v¬Q(x)vA(x) = 1
∀ x: ¬(¬P(x)v¬Q(x)) => A(x) = 1
∀ x: P(x)^Q(x) => A(x) = 1 (*)
Допустим
∃ y : (P(y)^Q(y) = 1) ^(A(y) = 0) = 1
Тогда
∃ y : P(y)^Q(y) => A(y) = 0
мы получаем противоречие с (*)
Таким образом, наименьшая область истинности предиката А(х) есть
пересечение областей истинности P(x) и Q(x) :-
[2,4,6,8,10,12]∩[4,8,12,116] = [4,8,12]
Ответ : 24
P(x) = { 1; x ∈ [2,4,6,8,10,12,14,16,18,20] ;
0; x!∈ [2,4,6,8,10,12,14,16,18,20]
}
Q(x) = { 1; x ∈ [3,6,9,12,15,18,21,24,27,30] ;
0; x!∈ [3,6,9,12,15,18,21,24,27,30]
}
Определить наибольшую область истинности предиката А(х),
как множество натуральных чисел таким образом,что
∀ x: (A(x) => ¬P(x))^(¬Q(x) => ¬A(x)) = 1
∀ x: (A(x) => ¬P(x))^(¬Q(x) => ¬A(x)) <=> (¬A(x)v¬P(x))^(Q(x)v¬A(x))
∀ x: (¬A(x)v¬P(x))^(Q(x)v¬A(x)) <=> ¬A(x)v¬P(x)^Q(x)
∀ x: ¬A(x)v¬P(x)^Q(x) = 1
∀ x: A(x) => ¬P(x)^Q(x)) = 1 (*)
Допустим
∃ y : (A(y)=1)^(¬P(y)^Q(y) = 0 ) = 1
Тогда
∃ y : A(y) => ¬P(y)^Q(y) = 0
мы получаем противоречие с (*)
Таким образом, наибольшая область истинности предиката А(х) есть
множество элементов области истинности Q(x), не принадлежащих
области истинности P(x) :-
[3,6,9,12,15,18,21,24,27,30]\[2,4,6,8,10,12,14,16,18,20] =
= [3,9,15,21,24,27,30]
Определим предикаты:-
P(x) = { 1; x ∈ [10,25] ;
0; x!∈ [10,25]
}
Q(x) = { 1; x ∈ [15,30] ;
0; x!∈ [15,30]
}
R(x) = { 1; x ∈ [25,40] ;
0; x!∈ [25,40]
}
Определить наибольшую область истинности предиката А(х),
такого что
∀ x: (Q(x) => ¬R(x))^A(x)^¬P(x) = 0
∀ x: (¬Q(x)v¬R(x))^A(x)^¬P(x) = 0
∀ x: (Q(x)^R(x))v¬A(x)vP(x) = 1
∀ x: A(x) => ((Q(x)^R(x)vP(x)) = 1 (*)
Допустим
∃ y : (A(y)=1)^(Q(y)^R(y))vP(y) = 0) = 1
Тогда
∃ y : A(y) => (Q(y)^R(y))vP(y)) = 0
Пoлучаем противоречие с (*)
Таким образом если обозначить области истинности
предикатов через $(A),$(P),$(Q),$(R) то А(х) будет
равен (Q(x)^R(x))vP(x)
и максимальной областью истинности предиката A(x)
будет $(A) = ($(Q)∩$(R))∪$(P) =
= ([15,30]∩[25,40]))∪[10,25] = [10,30]
*********************************************************
Пример задачи когда множество истинности
предиката А(х) не является связным
*********************************************************
Определим предикаты
Р(x) = { 1; x ∈ [5;30] ;
0; x !∈ [5;30]
}
Q(x) = { 1; x ∈ [14;33] ;
0; x !∈ [14;33]
}
Определить наибольшее множество истинности предиката А(х)
определенного на множестве действительных чисел R такого,что
∀ x∈R : (P(x)≡Q(x)) => ¬A(x)=True
Решение.
Поскольку (P(x)≡Q(x)) => ¬A(x) ≡ 1 то
(P(x)⊕Q(x)) v ¬A(x) ≡ 1
∀ x∈R : A(x) => P(x)⊕Q(x) = 1 (*)
Допустим
∃ y : (A(y)=1)^(P(y)⊕Q(y) = 0 ) = 1
Тогда
∃ y : A(y) => P(y)⊕Q(y) = 0
мы получаем противоречие с (*)
Таким обазом , наибольшее множество истинности предиката А(х)
есть ([5;30]\[14;33])∪([14;33]\[5;30]) = [5;14]∪[30;33]
По сути все клоны классической задачи 18 ипользуют
Утверждение 01
Пусть P и Q два одноместных предиката, определенных
На множестеве Х любой природы.
Если ∀ x ∈ Х : P(x) => Q(x) = True ,то область истинности
предиката P вложена в область истинности предиката Q
Ссылки
1. http://mathhelpplanet.com/static.php?p=primeneniye-logiki-predikatov
2. Техника исчисления базисных предикатов по Е.А. Мирончик 2017 и ЕГЭ Задача 18 ( поразрядная конъюнкция )
3. Shooting problems P-22,P-23,P-25 via "Calculus of basic predicates" by E.A.Mironchick 2017
Всюду в дальнейшем N+ означает множество неотрицательных
целых чисел.По умолчанию х всегда принадлежит N+
Определим предикаты
A(x) = { 1; x ∈ [70;90] ;
0; x !∈ [70;90]
}
B(x) = { 1; x ∈ [40;60] ;
0; x !∈ [40;60]
}
C(x) = { 1; x ∈ [0;N] ;
0; x !∈ [0;N]
}
F(x) = (¬A(x)=>B(x))^(¬C(x)=>A(x))
При каком наименьшем N область истинности F(x) содержит более 30 целых чисел
∀ x: (¬A(x)=>B(x))^(¬C(x)=>A(x)) <=> (A(x)vB(x))^(C(x)vA(x))
∀ x: (A(x)vB(x))^(C(x)vA(x)) <=> A(x)vB(x)^C(x)
Область истинности А(х) содержит 21 целое число.
Область истинности В(х)^C(x) есть [40;60]∩[0;N] и должна содержать не менее 11 целых чисел
Если N ∈ [40;60] то [40;60]∩[0;N]=[40;N]
При N-40+1 = 10 => N=49 ∈[40;60] область истинности
F(x) = A(x)vB(x)^C(x) содержит 31 целое число так как является объединением областей истинности А(х) и В(х)^C(x)
Следующие примеры из работы
К.Ю. Поляков Множества и логика в задачах ЕГЭ 2015
Ниже следуют решения задач №3,5,6 использующие алгебру предикатов :-
A(x) = { 1; x ∈ [x1;x2];
0; x !∈ [x1;x2]
}
P(x) = { 1; x ∈ [37;60] ;
0; x !∈ [37;60]
}
Q(x) = { 1; x ∈ [40;77] ;
0; x !∈ [40;77]
}
F(x) = P(x) => ((Q(x)^¬A(x)) => ¬P(x) ;
Определить наименьшую длину области истинности А(х)
∀ x: F(x)= P(x) => ((Q(x)^¬A(x)) => ¬P(x) = True
P(x) => ((Q(x)^¬A(x)) => ¬P(x) <=> ¬P(x)v¬Q(x)vA(x)v¬P(x)
P(x) => ((Q(x)^¬A(x)) => ¬P(x) <=> ¬P(x)v¬Q(x)vA(x)
∀ x : ¬P(x)v¬Q(x)vA(x) = 1
∀ x : ¬(¬P(x)v¬Q(x))=>A(x) = 1
∀ x : P(x)^Q(x) => A(x) = 1 (*)
Допустим
∃ y : (P(y)^Q(y) = 1) ^(A(y) = 0) = 1
Тогда
∃ y : P(y)^Q(y) => A(y) = 0
мы получаем противоречие с (*)
Таким образом, наименьшая область истинности A(x) есть пересение областей истинности P(x) и Q(x) , то есть [37;60]∩[40;77]=[40;60]
P(x) = { 1; x ∈ [2,4,6,8,10,12] ;
0; x!∈ [2,4,6,8,10,12]
}
Q(x) = { 1; x ∈ [4,8,12,116] ;
0; x!∈ [4,8,12,116]
}
Определить область истинности предиката А(х),
как множество натуральных чисел таким образом,что
∀ x: P(x) => ((Q(x)^¬A(x)) => ¬P(x)) = 1
∀ x: ((Q(x)^¬A(x)) => ¬P(x)) <=> (¬Q(x)vA(x)v¬P(x))
∀ x: ¬P(x)v¬Q(x)vA(x) = 1
∀ x: ¬(¬P(x)v¬Q(x)) => A(x) = 1
∀ x: P(x)^Q(x) => A(x) = 1 (*)
Допустим
∃ y : (P(y)^Q(y) = 1) ^(A(y) = 0) = 1
Тогда
∃ y : P(y)^Q(y) => A(y) = 0
мы получаем противоречие с (*)
Таким образом, наименьшая область истинности предиката А(х) есть
пересечение областей истинности P(x) и Q(x) :-
[2,4,6,8,10,12]∩[4,8,12,116] = [4,8,12]
Ответ : 24
P(x) = { 1; x ∈ [2,4,6,8,10,12,14,16,18,20] ;
0; x!∈ [2,4,6,8,10,12,14,16,18,20]
}
Q(x) = { 1; x ∈ [3,6,9,12,15,18,21,24,27,30] ;
0; x!∈ [3,6,9,12,15,18,21,24,27,30]
}
Определить наибольшую область истинности предиката А(х),
как множество натуральных чисел таким образом,что
∀ x: (A(x) => ¬P(x))^(¬Q(x) => ¬A(x)) = 1
∀ x: (A(x) => ¬P(x))^(¬Q(x) => ¬A(x)) <=> (¬A(x)v¬P(x))^(Q(x)v¬A(x))
∀ x: (¬A(x)v¬P(x))^(Q(x)v¬A(x)) <=> ¬A(x)v¬P(x)^Q(x)
∀ x: ¬A(x)v¬P(x)^Q(x) = 1
∀ x: A(x) => ¬P(x)^Q(x)) = 1 (*)
Допустим
∃ y : (A(y)=1)^(¬P(y)^Q(y) = 0 ) = 1
Тогда
∃ y : A(y) => ¬P(y)^Q(y) = 0
мы получаем противоречие с (*)
Таким образом, наибольшая область истинности предиката А(х) есть
множество элементов области истинности Q(x), не принадлежащих
области истинности P(x) :-
[3,6,9,12,15,18,21,24,27,30]\[2,4,6,8,10,12,14,16,18,20] =
= [3,9,15,21,24,27,30]
P(x) = { 1; x ∈ [10,25] ;
0; x!∈ [10,25]
}
Q(x) = { 1; x ∈ [15,30] ;
0; x!∈ [15,30]
}
R(x) = { 1; x ∈ [25,40] ;
0; x!∈ [25,40]
}
Определить наибольшую область истинности предиката А(х),
такого что
∀ x: (Q(x) => ¬R(x))^A(x)^¬P(x) = 0
∀ x: (¬Q(x)v¬R(x))^A(x)^¬P(x) = 0
∀ x: (Q(x)^R(x))v¬A(x)vP(x) = 1
∀ x: A(x) => ((Q(x)^R(x)vP(x)) = 1 (*)
Допустим
∃ y : (A(y)=1)^(Q(y)^R(y))vP(y) = 0) = 1
Тогда
∃ y : A(y) => (Q(y)^R(y))vP(y)) = 0
Пoлучаем противоречие с (*)
Таким образом если обозначить области истинности
предикатов через $(A),$(P),$(Q),$(R) то А(х) будет
равен (Q(x)^R(x))vP(x)
и максимальной областью истинности предиката A(x)
будет $(A) = ($(Q)∩$(R))∪$(P) =
= ([15,30]∩[25,40]))∪[10,25] = [10,30]
*********************************************************
Пример задачи когда множество истинности
предиката А(х) не является связным
*********************************************************
Определим предикаты
Р(x) = { 1; x ∈ [5;30] ;
0; x !∈ [5;30]
}
Q(x) = { 1; x ∈ [14;33] ;
0; x !∈ [14;33]
}
Определить наибольшее множество истинности предиката А(х)
определенного на множестве действительных чисел R такого,что
∀ x∈R : (P(x)≡Q(x)) => ¬A(x)=True
Решение.
Поскольку (P(x)≡Q(x)) => ¬A(x) ≡ 1 то
(P(x)⊕Q(x)) v ¬A(x) ≡ 1
∀ x∈R : A(x) => P(x)⊕Q(x) = 1 (*)
Допустим
∃ y : (A(y)=1)^(P(y)⊕Q(y) = 0 ) = 1
Тогда
∃ y : A(y) => P(y)⊕Q(y) = 0
мы получаем противоречие с (*)
Таким обазом , наибольшее множество истинности предиката А(х)
есть ([5;30]\[14;33])∪([14;33]\[5;30]) = [5;14]∪[30;33]
По сути все клоны классической задачи 18 ипользуют
Утверждение 01
Пусть P и Q два одноместных предиката, определенных
На множестеве Х любой природы.
Если ∀ x ∈ Х : P(x) => Q(x) = True ,то область истинности
предиката P вложена в область истинности предиката Q
Ссылки
1. http://mathhelpplanet.com/static.php?p=primeneniye-logiki-predikatov
