Evolution of Logic in Informatics and Computer Science
Logic of Informatics
Introduction
Historical view
•
Philosophical Logic
–
500 BC to 19th Century
•
Symbolic Logic
–
Mid to late 19th Century
•
Mathematical Logic
–
Late 19
th
to mid 20
th
Century
•
Logic in Computer Science
•
Logic is called the CALCULUS of Computer
Science!
•
LOGIC is a term for CS
CALCULUS is a term for Physical sciences &
Engineering Disciplines
•
Many CS areas use LOGIC, such as:
Architecture (logic gates)
Programming Languages ( Semantics & Logic
Programming)
AI
Databases (SQL)
Philosophical Logic
•
500 B.C – 19th Century
•
Logic dealt with arguments in the natural
language used by humans.
•
Example
–
All men are mortal.
–
Socrates is a man
–
Therefore, Socrates is mortal.
Philosophical Logic [2]
•
Natural languages are very ambiguous.
–
Eric does not believe that Mary can pass
any
test.
•
...does not believe that she can pass
some
test, or
•
...does not believe that she can pass
all
tests
–
I
only
borrowed your car.
•
And not ‘borrowed and used’, or
•
And not ‘car and coat’
–
Tom hates Jim and
he
likes Mary.
•
Tom likes Mary, or
•
Jim likes Mary
Symbolic Logic
•
Mid to late 19th Century.
•
The modern development of symbolic logic
begin with
George Boole
in the 19th century.
•
Attempted to formulate logic in terms of a
mathematical language
•
Rules of inference were modeled after various
laws for manipulating algebraic expressions.
Mathematical Logic
•
Late 19
th
to mid 20
th
Century
•
Frege proposed logic as a language for mathematics
in 1879.
•
With the rigor of this new foundation, Cantor was
able to analyze the notion of infinity in ways that
were previously impossible. (2
N
is strictly larger than
N)
•
Russell
’
s Paradox
T = { S | S ∉
S}
Logic in Computer Science
•
In computer science, we design and study
systems through the use of formal languages
that can themselves be interpreted by a
formal system.
–
Boolean circuits
–
Programming languages
–
Design Validation and verification
–
AI, Security. Etc.
Logic in Computer Science
•
Propositional Logic
•
First Order Logic
•
Higher Order Logic
•
Theory of Construction
•
Real-time Logic, Temporal Logic
•
Process Algebras
•
Linear Logic
Propositions Logic
•
A proposition is a statement that is either true
or false
–
2+2=4 (true)
–
New York City is in Oregon (false)
–
Today is Friday (its either true or false)
–
Do your homework! (not a proposition)
Compound and Primitive Propositions
•
Compound Propositions are propositions that
are composed of sub-propositions connected
together in various ways
–
roses are red and violets are blue
–
Mark is smart or he studies a lot
•
A
(atomic, elementary)
proposition
is the
underlying meaning
of a simple declarative
sentence, which is either true or false
Predicate logic
•
Extension of propositional logic
•
A ‘predicate’ is just a property
•
Predicates define relationships between
any number of entities
using qualifiers:
–
“for all”, “for every”
–
“there exists”
Example
•
Let
P
(
x
) be the property
‘if
x
is a triangle then the sum of its internal
angles is 180
o
”
•
In predicate logic:
x P
(
x
)
•
“For every
x
such that
x
is a triangle, the sum
of the internal angles of
x
is 180
o”
Another example
•
Let
P
(
x
) be the property
‘
x
is an integer and
x
2
= 4
’
•
Then
x P
(
x
)
•
“There exists
x
such that
x
is an integer and
x
2
= 4
”
Newton’s second law of motion
x: Object
stationary
(
x
)
in-uniform-motion
(
x
)
f : Force
x is-acted-upon-by f
In English: “for every
x
of a certain type referred to as an
Object
,
x
is
stationary,
x
is in uniform motion, or there is an
f
of type
Force
such that
x
is
acted upon by
f
”
“for every
x”
“of type called
object
”
“or”
“there exists an
f”
and
•
Remember:
x
‘for every
x
’, or ‘for
A
ll
x
’
x
‘there is an
x
’ or ‘there
E
xists an
x
’
Tip:
Think of
as an upside down ‘A’ (‘for
A
ll’)
Think of
as a backwards ‘E’ (‘there
E
xists’)
Propositional connectives
•
These are the words that we use to join
atomic propositions together to form
compound propositions. E.G:
In 1938 Hitler seized Austria, (
and
) in 1939
he seized former Czechoslovakia
and
in
1941 he attacked the former USSR
while
still having a non-aggression pact with it
Propositional connectives
•
Propositional logic has
four
connectives
Interpretation of connectives
Some more terminology…
•
Expressions either side of a conjunction are
called
conjuncts
(
p
q
)
•
Expressions either side of a disjunction are
called
disjuncts
(
p
q
)
•
In the implication
p
q
,
p
is called the
antecedent
and
q
is the
consequence
Precedence of connectives
•
In complex propositions, brackets may be
used to remove ambiguity.
(p
q)
r
versus
p
(q
r)
•
By convention,
the order of precedence
B
rackets,
N
egation,
C
onjunction,
D
isjunction,
I
mplication
Discrete Mathematical
Structures: Theory and
Applications
22
Mathematical Logic
•
Statement Formulas
–
Definitions
•
Symbols
p
,
q
,
r
,...,called statement variables
•
Symbols ~,
∧
,
∨
, →,and ↔ are called logical
connectives
1)
A statement variable is a statement formula
2)
If
A
and
B
are statement formulas, then the
expressions (~
A
), (
A
∧
B
) , (
A
∨
B
), (
A
→
B
) and (
A
↔
B
) are statement formulas
•
Expressions are statement formulas that are
constructed only by using 1) and 2) above
Although
both Stanley
and
Gordon are
not
young, Stanley has a better chance of winning
the next bowling tournament,
despite
Gordon’s
considerable experience
Formalisation
Formalisation (continued)
Atomic propositions:
p
– Stanley is young
q
– Gordon is young
r
– Stanley has a better chance of winning the next bowling
tournament
s
– Gordon has considerable experience in bowling
Formalisation in Propositional Logic:
(
p)
(
q)
r
s
Truth Table
•
A truth table for a compound statement is a list of
the truth or falsity of the statement for every
possible combination of truth and falsity of its
components.
•
In other words, a truth table helps to show
whether a statement is true or false.
Rows
•
To find the number of rows used in a truth
table, take the number 2 raised to the power
of the number of variables.
•
For example, if there was a p statement and a
q statement, there would be 2 variables, 2^2
is 4.
•
If there were three statements, it would be
2^3, or 8 rows.
Columns
•
The columns under the connectives /\, and \/,
stand for the conjunction, and disjunction of the
expression on the two sides of that connective.
Negation Truth Table
Conjunction Truth Table
Disjunction Truth Table
9/28/2024
31
Logical implication: IMPLIES
•
Is a proposition “if p, then q”.
•
Produces
all true
values
except when p is true and
q is false
.
•
Keywords: if-then, if, then, whenever, only if, etc.
•
We often use p q
•
The Truth table of
p → q
All
true
except
when
p is true
and
q
is false.
Discrete Mathematical
Structures: Theory and
Applications
32
Biimplication
–
Let p and q be statements. The statement “p if and
only if q” is called the
biimplication or biconditional
of p and q
–
The biconditional “p if and only if q” is written p
q
–
p
q is read:
•
“p if and only if q”
•
“p is necessary and sufficient for q”
•
“q if and only if p”
•
“q when and only when p”
Discrete Mathematical
Structures: Theory and
Applications
33
Biconditional [2]
–
Truth Table for the Biconditional:
Construct truth-tables for each of the
following formulae:
1.
P & (Q v ¬P)
2.
¬P → Q
3.
Q v ¬(P & Q)
4.
P → ¬(P & Q)
5.
P → (P v Q)
6.
Q → (P → Q)
7.
P & ¬P
8.
(Q v P) & ¬P
Explore the journey of logic from philosophical debates in ancient times to its crucial role in computer science today. From symbolic logic to mathematical foundations, discover how logic has shaped the development of formal systems and applications in various fields within the realm of informatics and computer science.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Logic of Informatics Introduction
Historical view Philosophical Logic 500 BC to 19th Century Symbolic Logic Mid to late 19th Century Mathematical Logic Late 19thto mid 20thCentury Logic in Computer Science
Logic is called the CALCULUS of Computer Science! LOGIC is a term for CS CALCULUS is a term for Physical sciences & Engineering Disciplines Many CS areas use LOGIC, such as: Architecture (logic gates) Programming Languages ( Semantics & Logic Programming) AI Databases (SQL)
Philosophical Logic 500 B.C 19th Century Logic dealt with arguments in the natural language used by humans. Example All men are mortal. Socrates is a man Therefore, Socrates is mortal.
Philosophical Logic [2] Natural languages are very ambiguous. Eric does not believe that Mary can pass any test. ...does not believe that she can pass some test, or ...does not believe that she can pass all tests I only borrowed your car. And not borrowed and used , or And not car and coat Tom hates Jim and he likes Mary. Tom likes Mary, or Jim likes Mary
Symbolic Logic Mid to late 19th Century. The modern development of symbolic logic begin with George Boole in the 19th century. Attempted to formulate logic in terms of a mathematical language Rules of inference were modeled after various laws for manipulating algebraic expressions.
Mathematical Logic Late 19thto mid 20thCentury Frege proposed logic as a language for mathematics in 1879. With the rigor of this new foundation, Cantor was able to analyze the notion of infinity in ways that were previously impossible. (2Nis strictly larger than N) Russell s Paradox T = { S | S S}
Logic in Computer Science In computer science, we design and study systems through the use of formal languages that can themselves be interpreted by a formal system. Boolean circuits Programming languages Design Validation and verification AI, Security. Etc.
Logic in Computer Science Propositional Logic First Order Logic Higher Order Logic Theory of Construction Real-time Logic, Temporal Logic Process Algebras Linear Logic
Propositions Logic A proposition is a statement that is either true or false 2+2=4 (true) New York City is in Oregon (false) Today is Friday (its either true or false) Do your homework! (not a proposition)
Compound and Primitive Propositions Compound Propositions are propositions that are composed of sub-propositions connected together in various ways roses are red and violets are blue Mark is smart or he studies a lot A (atomic, elementary) proposition is the underlying meaning of a simple declarative sentence, which is either true or false
Predicate logic Extension of propositional logic A predicate is just a property Predicates define relationships between any number of entities using qualifiers: for all , for every there exists
Example Let P(x) be the property if x is a triangle then the sum of its internal angles is 180o In predicate logic: x P(x) For every x such that x is a triangle, the sum of the internal angles of x is 180o
Another example Let P(x) be the property x is an integer and x2= 4 Then x P(x) There exists x such that x is an integer and x2 = 4
Newtons second law of motion of type called object for every x or x: Object stationary(x) in-uniform-motion (x) f : Force x is-acted-upon-by f there exists an f In English: for every x of a certain type referred to as an Object, x is stationary, x is in uniform motion, or there is an f of type Force such that x is acted upon by f
and Remember: x for every x , or for All x x there is an x or there Exists an x Tip: Think of as an upside down A ( for All ) Think of as a backwards E ( there Exists )
Propositional connectives These are the words that we use to join atomic propositions together to form compound propositions. E.G: In 1938 Hitler seized Austria, (and) in 1939 he seized former Czechoslovakia and in 1941 he attacked the former USSR while still having a non-aggression pact with it
Propositional connectives Propositional logic has four connectives Name Read as Symbol negation not conjunction and disjunction or implication if then
Interpretation of connectives Connective Interpretation negation pis true if and only if p is false A conjunction p q is true if and only if both p and q are true A disjunction p q is true if and only if p is true or q is true. An implication p q is false if and only if p is true and q is false The biconditional p if and only if q is written p q
Some more terminology Expressions either side of a conjunction are called conjuncts (p q) Expressions either side of a disjunction are called disjuncts (p q) In the implication p q, p is called the antecedent and q is the consequence
Precedence of connectives In complex propositions, brackets may be used to remove ambiguity. (p q) r versus p (q r) By convention, the order of precedence Brackets, Negation, Conjunction, Disjunction, Implication
Mathematical Logic Statement Formulas Definitions Symbols p ,q ,r ,...,called statement variables Symbols ~, , , ,and connectives 1) A statement variable is a statement formula 2) If A and B are statement formulas, then the expressions (~A ), (A B) , (A B ), (A B ) and (A B ) are statement formulas Expressions are statement formulas that are constructed only by using 1) and 2) above are called logical Discrete Mathematical Structures: Theory and Applications 22
Formalisation Although both Stanley and Gordon are not young, Stanley has a better chance of winning the next bowling tournament, despite Gordon s considerable experience
Formalisation (continued) Atomic propositions: p Stanley is young q Gordon is young r Stanley has a better chance of winning the next bowling tournament s Gordon has considerable experience in bowling Formalisation in Propositional Logic: ( p) ( q) r s
Truth Table A truth table for a compound statement is a list of the truth or falsity of the statement for every possible combination of truth and falsity of its components. In other words, a truth table helps to show whether a statement is true or false.
Rows To find the number of rows used in a truth table, take the number 2 raised to the power of the number of variables. For example, if there was a p statement and a q statement, there would be 2 variables, 2^2 is 4. If there were three statements, it would be 2^3, or 8 rows.
Columns The columns under the connectives /\, and \/, stand for the conjunction, and disjunction of the expression on the two sides of that connective.
Negation Truth Table p ~ p The opposite of p is ~p T F Not true is false F T Not false is true
Conjunction Truth Table p q p /\ q p and q True only if both are true. T T T T F F F T F F F F
Disjunction Truth Table p q p \/ q p or q True if either on is true T T T T F T F T T False only if both are false F F F
Logical implication: IMPLIES Is a proposition if p, then q . Produces all true values except when p is true and q is false. Keywords: if-then, if, then, whenever, only if, etc. We often use p q The Truth table of p q All true except when p is true and q is false. 9/28/2024 31
Biimplication Let p and q be statements. The statement p if and only if q is called the biimplication or biconditional of p and q The biconditional p if and only if q is written p q p q is read: p if and only if q p is necessary and sufficient for q q if and only if p q when and only when p Discrete Mathematical Structures: Theory and Applications 32
Biconditional [2] Truth Table for the Biconditional: Discrete Mathematical Structures: Theory and Applications 33
Construct truth-tables for each of the following formulae: 1. P & (Q v P) 2. P Q 3. Q v (P & Q) 4. P (P & Q) 5. P (P v Q) 6. Q (P Q) 7. P & P 8. (Q v P) & P
