✓
Domain: {1,2,3}
𝑃(𝑥, 𝑦) = 𝑥 ≥ 1 ∧ 𝑦 ≥ 1
Domain: {1,2,3} 𝑃(𝑥, 𝑦) = 𝑥 > 𝑦
Domain: {1,2,3} 𝑃(𝑥, 𝑦) = 𝑥 > y 𝐹 ∨ 𝐺 is not true
✓
∀𝑥(𝐷(𝑥) ∧ ∀𝑦(𝑃(𝑦) ⇒ 𝐸(𝑥, 𝑦)) ⇒ ∀𝑧 (𝐶(𝑧) ⇒ ¬𝐹(𝑧, 𝑥)))
{{𝐷(𝑓(𝑥, 𝑦)), ¬𝑀(𝑦), ¬𝐿(𝑦, 𝑦)}, {¬𝐿(𝑦, 𝑓(𝑥, 𝑦)), ¬𝑀(𝑦), ¬𝐿(𝑥, 𝑦)}}
{𝐹(𝑐,𝑏)} {¬𝐹(𝑥,𝑦),𝐹(𝑦,𝑥)} {¬𝐹(𝑥,𝑦),𝐿(𝑥,𝑦)} {𝐿(𝑏,𝑥),¬𝐿(𝑥,𝑐)} {¬𝐿(𝑏,𝑏)} {𝐹(𝑏, 𝑐)}
{𝐿(𝑏, 𝑐)}
{𝐿(𝑏, 𝑏)}
⊥
✓✓ ✓
𝑏
𝑎
𝑏
𝑏
𝑎
𝑎
𝑎,𝑏
𝑎 𝑏
𝑎∗ ∪ 𝑏∗
1
aa 2,4,5
a 4,5
b a,b
bb
abb 3,5 5
a
𝑎𝑎∗𝑏∗
(𝑎 ∪ 𝑏)∗
Base cases:
18 = 4 + 7 + 7
19 = 4 + 4 + 4 + 7
20 = 4 + 4 + 4 + 4 + 4
21 = 7 + 7 + 7
Suppose for some 𝑛 ≥ 21, that ∀𝑘 (18 ≤ 𝑘 ≤ 𝑛 ⇒ 𝑆(𝑛))
Since 𝑆(𝑛 − 3) is true, we know 𝑛 + 1 can be written as a sum of 4s and 7s, as we take a sum of 4s and 7s for 𝑛 − 3 and add a 4. Thus, we know 𝑆(𝑛 + 1) is true.
We can conclude that 𝑆(𝑛) is true for all 𝑛 > 17
𝑆 → 𝑆𝑎𝑎𝑎𝑎 → 𝑆𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 → 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎
𝑆 → 𝑆𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 → 𝑆𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 → 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎
𝑆→𝜖|𝑎4 |𝑎7 |𝑎7 |𝑎11 |𝑎14 |𝑎16 |𝑎18𝐴 𝐴 → 𝜖 | 𝑎𝐴
∀𝑥 (∀𝑦 (𝑦 ∈ 𝐹 ⇒ 𝑥 ∈ 𝑦) ⇒ ∃𝑧 (𝑧 ∈ 𝐺 ∧ 𝑥 ∈ 𝑍))
∗∗∗∗∗∗ 𝜖∈(𝐿\𝑀)∧𝜖∉𝐿\𝑀⇒(𝐿\𝑀) ⊈𝐿\𝑀
𝐿 = {𝑎,𝑏},𝑀 = {𝑎}
∗∗∗ 𝑎𝑏 ∉ (𝐿\𝑀) , 𝑎𝑏 ∈ 𝐿 \𝑀
isTotalFct :: Int -> [(Int, Int)] -> Bool isTotalFct n r = [0..n] == map fst (sort $ nub r)
isIdempotent :: Int -> [(Int, Int)] -> Bool isIdempotent _ r = all (flip elem r) (map (dup . snd) r)
where dup a = (a, a)
𝑎,𝑅 𝑎,𝑅 𝑎,𝑅 𝑎,𝑅 𝑏,𝑅 𝑏,𝑅 𝑏,𝑅 𝑏,𝑅
𝑎,𝑅 𝑏,𝑅
𝑎,𝑅
𝑎,𝐿 𝑏,𝐿
_,𝐿 𝑏,𝐿
𝑎,𝐿 𝑏,𝐿
𝑎,𝐿