1 of 43

Truth, Deduction, Computation

Introduction

1

Vlad Patryshev

SCU

2019

http://tinyurl.com/coen260-1

Add: mythological thinking

Add: IZF

Add: https://en.wikipedia.org/wiki/Pocket_set_theory

Add: https://toldot.ru/urava/ask/urava_9320.html

2 of 43

Logic: Variety of Interpretations

different in different cultures

China
India
Greece
Modern European culture

depends on where you apply it

legal
iq test
math
religion
comp sci

2

3 of 43

Logic in China

3

Mozi (墨子) (468-376 BC) , School of Mohism

Three validity tests: ancient authority, common observation, and practical effect.

The statement "All statements are mistaken" implies that it is itself mistaken, and one cannot "reject rejection" without refusing to reject one's own rejection.

"The ghost of a man is not a man," but "The ghost of my brother is my brother."

"A robber is a man, but abounding in robbers is not abounding in men, nor is being without robbers being without men." https://www.sciencemag.org/news/2017/06/china-s-quantum-satellite-achieves-spooky-action-record-distance

Guō Mòruò (郭沫若) called him a facsist.

GōngSūn Lóng (公孫龍) 325–250 BC, School of Names

"One and one cannot become two, since neither becomes two."�“White horses are not horses”

“A planet can be any size. A planet can be giant or very small. A dwarf planet can only be very small. Therefore, one can say that a dwarf planet is not a planet.”

(Later, though, the only allowed logic was Buddhist logic imported from India)

4 of 43

4

5 of 43

Logic in India

Tetralemma (Catuṣkoṭi, चतुष्कोटि): for a proposition X, there are four possibilities: X; not X; X and not X; not (X or not X)

5

Positive configuration	Negative configuration
P	Not (P)
Not-P	Not (Not-P)
Both P and Not-P	Not (Both P and Not-P)
Neither P nor Not-P	Not (Neither P nor Not-P)

dharmachakra (धर्मचक्र)

(“wheel of laws”)

6 of 43

India: Navya-Nyaya School (13th century)

Syadvada - “could-be-ism” (in Jaina logic)

1.Syād-asti — “maybe it is”

2.Syād-nāsti — “maybe it is not”

3.Syād-asti-nāsti — “maybe it is, maybe it is not”

4.Syād-asti-avaktavyaḥ — “maybe it is, hard to tell”

5.Syād-nāsti-avaktavyaḥ — “maybe it is not, hard to tell”

6.Syād-asti-nāsti-avaktavyaḥ — “maybe it is, maybe it is not, hard to tell”

7.Syād-avaktavyaḥ — “it may be hard to tell”

6

7 of 43

Navya-Nyaya Epistemology

The central concern of Indian logic as founded in Nyāya is epistemology, or the theory of knowledge.

Navya-Nyāya lists seven ‘categories’ (padārtha) of object:

substance (dravya)
quality (guṇa)
motion or action (karma)
universal (sāmānya)
particularity or differentiator (viśeṣa)
inherence (samavāya)
absence (abhāva) (added later)

7

8 of 43

Logic in India: an Example

8

Yudhisthira (युधिष्ठिर)

Yudhisthira never said a lie, and as a reward, his chariot was not touching the earth.

Once Lord Krishna asked him to tell guru Drona about Ashwathama being killed by Bhima. Drona’s son’s name was Ashwathama, but it was actually an elephant with the same name that Bhima killed.

Yudhisthra said “Ashwathama was killed, a man or an elephant”.

The moment Yudhisthira pronounced a statement that was partially a lie, though it was true as a whole, his chariot came down.

9 of 43

Jewish Logic

Non-deductive Inferences in the Talmud
How the Talmud defines Sets
Talmudic Deontic Logic
Temporal Logic in the Talmud
Resolution of Conflicts and Normative Loops in the Talmud
Talmudic Logic

Example: Kal va-chomer (קל וחומר) (a fortiori, in Latin, kaimutya nyaya in Nyaya)

If a parent will punish his or her child with a minor punishment should the latter return home with scuffed shoes, surely the parent will punish his or her child with a major punishment should the latter return home with scuffed shoes, ripped pants and a torn shirt. This is an illogical deduction

Why:

Leviticus 18:21 speaks of the prohibition of worshiping Molech, a form of worship in which children were passed through fire (presumably until dead). - but if you fry them all, which is stronger, it beats the purpose, so it’s legal. You are not allowed to sacrifice some of your kids for the sake of your enterprise, but if you fry them all, what’s the point?

// see also a discussion in http://minski-gaon.livejournal.com/100791.html (Russian)

(Есть очень хорошие исследования проф. Габая. Есть по русски ъорошая книжка С.Долгопольского про риторику Талмуда. )

9

Deontic logic is the field of logic that is concerned with normative concepts. such as obligation, permission, and prohibition.

10 of 43

Logic in Greece

10

Aristotle (Ἀριστοτέλης) 384–322 BC

Syllogisms

Every man is a being therefore:
Every non-being is a non-man
A chimera is not a man therefore:
A non-man is not a non-chimera

See also enthymeme (same thing as syllogism)

11 of 43

Renaissance Europe

Pierre Abélard (France, 1079–1142)

Must human faith be completed by reason, or not?
Does faith deal only with unseen things, or not?
Is there any knowledge of things unseen, or not?
May one believe only in God alone, or not?
Is God a single unitary being, or not?

William of Ockham (England, 1285–1349)

(non sunt entia multiplicanda praeter necessitatem)

Jean Buridan (France, c. 1300-post 1358)

(remember the donkey?)

11

12 of 43

Western Europe, XIX-XX centuries

12

Georg Cantor, 1845-1918

“No matter how correct a mathematical theorem may appear to be, one ought never to be satisfied that there was not something imperfect about it until it also gives the impression of being beautiful.”

“In mathematics the art of asking questions is more valuable than solving problems.”

“The essence of mathematics lies in its freedom.”

13 of 43

Finals

Questions

Year 1862

13

14 of 43

Europe/US, XX century

14

David Hilbert, 1862-1943

“No one shall expel us from the paradise that Cantor has created for us.”

Kurt Gödel, 1906-1978

“The more I think about language, the more it amazes me that people ever understand each other at all.”

“The brain is a computing machine connected with a spirit.”

Paul Cohen,

1934–2007

(independence of continuum hypothesis)

Alexander Esenin-Volpin,

1926-2016

“Numbers bigger than 10¹¹ should be considered infinite”

15 of 43

XXI century

15

Gregory Chaitin, b.1947

"there are mathematical facts that are true for no reason, they're true by accident. They are random mathematical facts"

Saul Kripke, b.1940

“Lois Lane believes that Superman can fly, although she does not believe that Clark Kent can fly.”

“Londres est joli”

Per Martin-Löf,

b. 1942

(intuitionistic type theory)

Vladimir Voevodsky (1966-2017)

(Homotopy Type Theory)

16 of 43

Applications: Legal (and media)

Deductive reasoning:

“All people cheat, so students must cheat”

Inductive reasoning:

Jane studies every day and is a good student.
Tom studies every day and is a good student.
Angela studies every day and is a good student.
Hence: Good students study every day.

Search for Fallacies:

“Example: “The possession of nuclear weapons is a moral abomination. Even Edward Teller, the ‘father of the hydrogen bomb,’ urged the United States to halt production once the full extent of their destructive power became known.”
Why not: While it may seem persuasive that even the “father” of the hydrogen bomb disapproved of its development, note that Teller was a physicist, not a cleric or moral philosopher. His views on morality are completely outside his expertise.”

16

17 of 43

Applications: Legal

Kurt Goedel found a glitch in US Constitution, due to which dictatorship is possible in US - see this�Fortunately, the proof was lost�So nobody knows now how a dictatorship can be established in US
A scientist filed a libel suit agains other scientists that publicly criticized his work: link
“Courts Don’t Determine Scientific Facts”
Two men are suspected of murder. By the axiom of choice one of them is guilty. By the law, none is.

17

18 of 43

Applications: Religions

Proofs of God’s existence:

Deductive

God is the greatest conceivable being.
It is greater to exist than not to exist.
Therefore, God exists.

Karmic: some people in this world are happy, some are in misery - therefore, God exists

Proofs of God’s nonexistence:

Deductive

Can God create a rock so big that God cannot move?

Inductive

A perfect being would have long ago satisfied all its wants and desires and would no longer be able to take action in the present without proving that it had been unable to achieve its wants faster—showing it imperfect.

18

19 of 43

Applications: IQ Tests

E.g.

A Division Director scheduled six meetings on Wednesday with his direct reports: Anita, Harold, Ben, Markus, Sheila, and Carol. Each meeting is with only one direct report, and each direct report will meet only once with the Division Director. The Division Director labeled the meeting timeslots in order from 1 through 6, with timeslot 1 occurring first and timeslot 6 occurring last.

Ben's meeting will be immediately after Harold's.

Anita's meeting will be two meetings after Markus'.

Anita's meeting will be before, but not immediately before, Carol's.

Which direct report is in timeslot 2?

Anita? Harold? Ben? Markus? Sheila?

19

20 of 43

Applications: Common Sense

E.g. Wason selection task

Paradoxes and Fallacies

Contradiction

The sentence below is true.
The sentence above is false.

There is someone in the pub such that, if he is drinking, everyone in the pub is drinking.
"the first number not nameable in under ten words"
Pinocchio paradox: What would happen if Pinocchio said "My nose will be growing"?

(see also: List of Fallacies on wikipedia)

20

21 of 43

Applications: Common Sense

Misconceptions

Every statement is either right or wrong
Axioms are true, and this is why theorems that follow from axioms are also true
Every logic is Boolean or can be expressed in Boolean
Boolean logic has only two values
Programs only deal with finite entities

21

22 of 43

More Common Sense

Which of these statements make sense?

All the Solar System planets rotate around the Sun. The Earth rotates around the Sun. Hence The Earth belongs to the Solar System.�
God created Everything. The Earth is a part of Everything. Hence God created the Earth.�
"I think that any human who does not have special problems with reading and understanding can, based on my two long comments, answer the question whether it is true that I state that "to know intimately" cannot be understood in the sense of sex."

22

23 of 43

Scott Adams’ Trolling Class

23

24 of 43

Applications: Politics

Assignment (0 points):

Find examples from Trump’s tweets

24

25 of 43

Applications: Hardware

25

26 of 43

Applications: Software

Binary logic (used in circuits) and Ternary (Сетунь, a Soviet computer from the ‘70-s)
Untyped lambda calculus and typed lambda calculus; Curry-Howard isomorphism
Logic programming (e.g. Prolog)
Theorems for Free (Girard-Reynolds): e.g. �if f:A×B -> A for all possible A and B, �then f(a,b) == a.

26

27 of 43

Applications: Coding

Bent Function - hard to approximate function�{⊤, ⊥}ⁿ → {⊤ ⊥}

Cryptography (change one input bit, half output bits will change)
CDMA (not actually, but could - GPS, mobile phones)
Other Spread Spectrum technologies

27

28 of 43

Set Theory and SQL

select * from users where age < 18;

28

29 of 43

Sets, Informally

a ∈ A : a is an element of A
empty set ∅ ≡ ¬∃x (x∈∅)
A ⊂ B ≡ ∀x ((x∈A)→(x∈B))
A ⊄ B ≡ ¬(A⊂B)
{x∈A | P(x)} : set comprehension
A ∩ B = {x | (x∈A) ∧ (x∈B)}
A ∪ B = {x | (x∈A) ∨ (x∈B)}
A \ B = {x | (x∈A) ∧ ¬(x∈B)}
powerset P(A) ≡ {B | B ⊂ A} e.g. P(∅)={∅}; P(P(∅))={∅,{∅}}

29

self-contradictory

30 of 43

Sets, formally: ZFC Axioms

Extensionality Axiom
Axiom of Empty Set
Comprehension Axiom Schema (filter)
Axiom of Pair
Axiom of Union
Replacement Axiom Schema (map)
Axiom of Infinity
Powerset Axiom
Foundation Axiom
Axiom of Choice

30

non-contradictory

31 of 43

Examples: Two-valued Boolean Logic

31

&	True	False
True	True	False
False	False	False

\|	True	False
True	True	True
False	True	False

	!
True	False
False	True

32 of 43

Examples: 8-valued Boolean Logic

32

^	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	0	1	0	1	0	1
2	0	2	2	0	0	2	2
3	1	2	3	0	1	2	3
4	0	0	0	4	4	4	4
5	1	0	1	4	5	4	5
6	0	2	2	4	4	6	6
7	1	2	3	4	5	6	7

	!
0	7
1	6
2	5
3	4
4	3
5	2
6	1
7	0

33 of 43

Examples: 3-Valued Kleene Logic

33

&	True	Unknown	False
True	True	Unknown	False
Unknown	Unknown	Unknown	False
False	False	False	False

\|	True	Unknown	False
True	True	True	True
Unknown	True	Unknown	Unknown
False	True	Unknown	False

	!
True	False
Unknown	Unknown
False	True

34 of 43

Examples: 3-Valued Heyting Logic

34

&	True	Unknown	False
True	True	Unknown	False
Unknown	Unknown	Unknown	False
False	False	False	False

\|	True	Unknown	False
True	True	True	True
Unknown	True	Unknown	Unknown
False	True	Unknown	False

	!
True	False
Unknown	False
False	True

35 of 43

Other Interesting Logics Systems

Linear logic: $1 and $1 != $1

(see "Physics, Topology, Logic and Computation: A Rosetta Stone")

Modal logic (‘Ask three modal logicians what modal logic is, and you are likely to get at least four different answers’)
Fuzzy Logic
Temporal logic
Higher order logics
Quantum logic

35