Logic - 2018-04-18

In boolean logic, a disjunctive normal form (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a cluster concept. As a normal form, it is useful in automated theorem proving. == Definition == A logical formula is considered to be in DNF if and only if it is a disjunction of one or more conjunctions of one or more literals. A DNF formula is in full disjunctive normal form if each of its variables appears exactly once in every conjunction. As in...

ko means ko

Kasmir Khaan

knockout? :D

let me try and see what i see :D

@LeakyNun but is my idea bad? of the split?

Leaky Nun

I don't know, just try it

Kasmir Khaan

okay :D

Kasmir Khaan

3:25 AM

@LeakyNun it is not a tautology !

Leaky Nun

Kasmir Khaan

the first half is obviously not because

if P_1 and P_3 are false

then we get a 0

the second one i did it with truth table and found many 0 's as well :D

@LeakyNun did you solve it as well ? or just said ok ? :D

Leaky Nun

I didn't solve it

Kasmir Khaan

grrr leaky how i know i did it right then

Leaky Nun

but they aren't asking iff

Kasmir Khaan

3:27 AM

i know

i split the problem

the middle "OR"

if the two smaller pieaces are not tautologies then the bigger pieace is not

if one of them is however , then the while expression is also tauto

Leaky Nun

@KasmirKhaan that's false

Kasmir Khaan

hmm why ?

Leaky Nun

neither P nor !P are tautologies

Kasmir Khaan

we have inclusive or

Leaky Nun

but P|!P is a tautology

Kasmir Khaan

3:29 AM

hmm ><

true

how else does one do this then

grrrrrrrrrr

Leaky Nun

I already told you

Kasmir Khaan

by sum and product you mean "and" and "or" ?

can any expression be written using those two ?

@LeakyNun

Leaky Nun

and not

so (!P1 & P2 & P3) | (P1 & P3) | P4 is in SOP

Kasmir Khaan

what SOP ?

and we dont have P_4

Leaky Nun

sum of product

Kasmir Khaan

3:34 AM

GRRR @LeakyNun thanks for help leaky :D i think i need to sleep its 5 am here ><

ill continue tomorrow

Leaky Nun

Kasmir Khaan

14 hours later…

user21820

5:05 PM

@LeakyNun Interesting. (But I never understood what was so important about confluence, and Google doesn't tell me much. I understand that strong normalization is very useful to have, if we want some things like decidable equality.) As for the proof, here is my proof sketch by strong induction:

Let ~> be the transitive closure of beta-reduction (one or more reductions).
Let size(e) be the length of expression e (counting lambdas plus applications).
Given expressions p,q,r such that p ~> q and p ~> r:
	If p = (x->i) for some expression i and variable x:
		q = (x->j) and r = (x->k) and i ~> j and i ~> k for some expressions j,k.
		size(i) < size(p).
		Thus by induction j ~> l and k ~> l for some expression l.
		Thus q ~> (x->l) and r ~> (x->l).
	If p = i(a) for some expressions i,a:
		If q = j(a) and r = i(b) and i ~> j and a ~> b for some expressions j,b:

4 hours later…

Kasmir Khaan

8:50 PM

@user21820 please text me when you are here :D

3 hours later…

Kasmir Khaan

11:26 PM

@AlessandroCodenotti hi here? :D

I need help with natural deduction

in propositional logic