(upbeat music)
- Hi, my name is Alexander Knop
and this is introduction
to mathematical logic.
If you have not seen the introduction
to mathematical reasoning, I
recommend you to have a look.
Mathematical logic is
a branch of mathematics
that's studying mathematics itself.
In other words, it's studying proofs.
In this short class, we are going to
study the basics of this vast field.
In order to study
something mathematically,
we need to give a formal definition.
In the first part, we are
going to study a simple model
which is called propositional logic.
In the second part, we are
going to study a bit more
involved model, which is
called the predicate logic.
In this video we are going
to define what it means
a statement in a propositional logic.
In other words, we are going to define
propositional formulas.
So phi is a propositional formula
on the variables x_1, ..., x_n,
if either phi is x_i
for some i
from 1 to n or it's a
negation of another formula.
Or phi is a conjunction, or dysjunction
or implication of two other formulas,
psi_1 and psi_2.
And both of them should
be propositional formulas
on x_1, ..., x_n.
If you have a formula, it should be a way
to compute the value of this formula.
So let phi be a formula
on x_1, ..., x_n
and v_1, ..., v_n be
some true or false values
for x_1, .., x_n.
So we are going to consider
three cases like this,
and in each case we are going
to define the value of phi.
So if phi is equal to x_i, then
the value of phi
is equal to v_i.
If phi is equal to the negation of psi,
then the value of phi
is equal to the negation
of the value of psi.
Finally, if phi is psi_1 sharp psi_2,
then the value of phi
is equal to sharp of the
values of psi_1 and psi_2.
Let's consider an example.
Imagine that we have a formula phi
equal to x one or x two, and x three,
and we wish to find the value of it
with v one equal to true,
v two equal to false, and v
three equal to true again.
Note that the value of x_1 under
this substitution is true.
The value of x_2 is false,
and the value of of x_3
is true again, hence,
the value of x_1 or x_2 is
true or false, which is true.
And finally, the value of phi
is true and true, which is true again.
Let's prove some simple
theorem about the formulas.
For example, we can prove that
the formulas are kind of associated.
In other words, if you
have three formulas,
A, B, and C, on the same variables.
Then A or B or C is the
same as A or B or C.
For any values of v_1, ..., v n.
And the same can be proven for n.
How can we prove this?
So let a be the value of A,
b be the value of B,
and c be the value of C.
In this case, the value of (A or B) or C
is equal to (a or b) or c,
but at the same time
it's equal to a or (b or c),
which is the value of A or (B or C),
and it proves the first statement.
Similarly, you can replace
everwhere dysjunctions
by conjunctions and prove
the second statement.
Since we have some kind of activity,
we can define dysjunction and conjunction
of more than one formula.
So let phi one to phi n
be formulas on x_1, ..., x_n.
Then, conjunction of
phi_i's for i from 1 to n
is phi_1 and phi_2 and
dot dot dot dot dot dot.
And dysjunction of
phi_i's, i from one to n,
is phi_1 or phi_2
or phi_3 or dot dot dot.
Using this notation we
can show that any function
can be represented as a
propositional formula.
In other words, the value of a function
is equal to the value of a formula
for all values v_1, ..., v_n.
In order to prove this, let's
give the formal definition.
x_i^s is equal to x_i,
if s is true,
and not x_i if s is false.
In this case, you may notice that
if you have a conjunction, from one to n
of x_i^(s_i),
then it's equal to true,
if and only if,
s_1 is equal to v_1,
..., s_n is equal to v_n.
Okay, so now we know how to satisfy
one substitution and exactly one.
Now let's write s_(1,1), ..., s_(1,n)
..., s_(k,1), ..., s_(k,n),
be all s_1, ..., s_n
such that f(s_1, ..., s_n) is true.
In other words, it's all the
assignments to the function f
such that it's satisfied, it's true,
then f(v_1, ..., v_n)
is always equal to the disjunction
for j from 1 to k of conjunctions
for i from 1 to n of
x_i^(s_(j,i)).
Indeed, if you substitute
one of these values,
this is satisfied
because the corresponding
conjunction is satisfied.
If you substitute something else,
none of them is satisfied
and both of them are false.
This formula is called a disjunctive
normal form of a function f.
And it shows that this theorem is true.
In this video, we
discussed how to formalize
the notion of a statement
in the propositional logic.
In the next two videos,
we are going to discuss
how to prove them in
the propositional logic.
If you have any questions,
ask them in the comments.
See you later.
(music)
