"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

Tuesday, April 26, 2011

PROPOSITIONAL CALCULUS (Propositional Logic, Sentential Calculus, Sentential Logic) Emulator/Calculator

The Propositional Calculus Calculator (Propositional Logic Calculator) has been written in Matlab. So you'll need Matlab to run it. Just download the m.files from the links provided below and you're ready to use it. Alternatively copy the actual code which I pasted at the end of this post.

Using the truth tables, or truth trees (semantic trees) approach to evaluating formulae and arguments becomes a rather laborious task as the number of propositional variables (PV's) increases, and the number of interpretations grows exponentially i.e.

Number of interpretations = 2Number of PV's
 
With this software you can evaluate a formula of any length and complexity in no time. It will take you longer to actually enter the formula, then the program to evaluate it.


The most relevant applications it has are:
tautology.m 
valid.m
consistent.m

Below are screenshots of the executed files upon entering relevant input. You'll need to read the syntax directions to get the idea how this is done. I'm posting them further below. You can download all the files from links provided at the end of this post.

The output here is self explenatory - 1 stands for affirmative.



Not a tautology, and we read the output as the counter-model (counter-example) being the following interpretation:
v(p1) = 1, v(p2) = 0, v(p3) = 0



Wow! - Modus Ponens is valid - this thing works!



Again, for any contingency or in this case invalid inference a counter-model is provided (one is sufficient):
 v(p1) = 0, v(p2) = 1


Here, since the set is consistent we're given the model (interpretation) that satisfies it:
v(p1) = 1, v(p2) = 1, v(p3) = 0, v(p4) = 0



Some comments on the input notation. The propositional binary functions we use are of the form:

 
 
Hence the negation, a unary function is just an operator on the set {0,1}:

 
So the notation in the program is naturally motivated. It is a functional notation.Hence complex formulae are just compositions of functions.


DOWNLOAD 

Click on any of the links below to download The Propositional Calculus Calculator m.files. Make sure to download all 23 files!


Comments and feedback are welcome :)

INSTRUCTIONS
--------------------------------------------------------------------------------------
If you prefer the intuitive approach and don't want to read all the instructions
(which takes less than 5 minutes, and you should eventually!):

Just try entering for the wff ((p1 & p2) ==> ~p1), the following expression:
(I suggest a cut-and-paste approach):

tautology('conf(orf(p1,notf(p2)),notf(p1))')  

and see what happens :)

Or try testing the inference {p1,(p1 ==> p2),p3} |= (p2 & p3), with the following:

valid('p1,conf(p1,p2),p3','andf(p2,p3)')

and see what happens :)

Or finally try testing the consistency of the set {p1,p2,(p1 v p3),~p3,(p3<==>p4)}
by entering:

consistent('p1,p2,orf(p1,p3),notf(p3),bconf(p3,p4)')

--------------------------------------------------------------------------------------
BUT, I DO ENCOURAGE YOU TO READ THE FOLLOWING:
--------------------------------------------------------------------------------------
SYNTAX
--------------------------------------------------------------------------------------
We have the standard functions:

notf(...) = NOT (a function whose domain/input is a single variable)

orf(...,...) = OR (all dyadic functions have a two variable domain/input)

andf(...,...) = AND

conf(...,...) = MATERIAL CONDITIONAL

bconf(...,...) = MATERIAL BICONDITIONAL

Before I will recursively define the language, note that in this program all
the wff's will have to be entered as strings i.e. 'whatever' is the input in
Matlab to convert the word whatever into a string array.

--------------------------------------------------------------------------------------
RECURSIVE DEFINITION OF THE LANGUAGE
--------------------------------------------------------------------------------------
B: any Propositional Variable is a wff i.e. p1, p2, p3, ...

HOWEVER! in any complex wff use the minimun number of distinct pv's
that is: do not use a pv with higher ordering then necessary
example: instead of (p3 v p27) ==> (p27 & p456) use (p1 v p2) ==> (p2 & p3)

R1: if A is a wff then notf(A) is a wff

R2: if A and B are wff's then orf(A,B) is a wff

R3: if A and B are wff's then andf(A,B) is a wff

R4: if A and B are wff's then conf(A,B) is a wff

R5: if A and B are wff's then bconf(A,B) is a wff

T: nothing else is a wff
--------------------------------------------------------------------------------------
META-FUNCTIONS
--------------------------------------------------------------------------------------
In order to get anything working in this emulator you'll have
to use one of the following functions:

tautology(...)
- enter some some wff as a string

valid(...,...) - first string is a list of premises wff's, and the second string is the conclusion wff

consistent(...) - just a string listing some wff's

And remember - all ... entries are strings i.e. tautology('orf(p1,notf(p1))') - note the dashes
Remember that 'orf(p1,notf(p1))' is the input in Matlab to convert the expression orf(p1,notf(p1)) into a string array.

The tautology function, tells you whether some wff is a tautology or not,
plus gives a single counterexample (one is enough!)

The valid function, tells you whether an argument is valid or not,
plus gives a single counterexample

The consistent function determines whether the set of wff's is satisfiable by some interpretation

NOTE: for n pv's a model or counter-model of the form 0 0 1 0 ... 1
is to be interpreted as val(p1)=0, val(p2)=0, val(p3)=1, val(p4)=0, ..., val(pn)=1

NOTE: this program has not been optimized for efficiency, so for wff's containing in excess of
12 distinct propositional variables the execution time could take around 2 minutes, depending
on your CPU.
--------------------------------------------------------------------------------------
Have fun! This package certainly helps evaluating long wff's.
If you find any bugs, or have some suggestions, leave a comment below :)
--------------------------------------------------------------------------------------
Mariusz
--------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------
Propositional Logic Calculator, Propositional Calculus Calculator, Propositional Logic Emulator, Propositional Calculus Emulator, Propositional Logic Simulator, Propositional Calculus Simulator, 
Propositional Logic Application, Propositional Calculus Application, Propositional Logic Applet
Propositional Calculus Applet.
--------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------
COMPLETE CODE
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=wff(x)
%x is the string array of the wff with pv's expressed as p1, p2,...
b=convert3(x);
a=char(b(1:length(b)-4));
npv=b(length(b)-3);
if b(length(b))~=0 || b(length(b)-1)~=0 || b(length(b)-2)~=0
    y=[7,b(length(b)-2),b(length(b)-1),b(length(b))];%this condition obtains when a
    %syntax error has been detected
else
%a will be the new wff string with pv's expressed as p(v,1),p(v,2),...
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%now for 2^2*npv rows we evaluate the wff with the values for v iterating
%over the number of rows. But we also need the truth table p.
p=truth_table(npv);
eval_array=zeros(1,2^npv);
for v=1:2^npv
    eval_array(v)= eval(a);
end
y=[eval_array,b(length(b)-2),b(length(b)-1),b(length(b))];
end
end


%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y = is_even(x)

if floor(x/2)==x/2
    y=1;
else
    y=0;
end
end
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=n_andf(x)
t=0;
for k=1:length(x)
    if x(k)==0
        t=t+1;
    end
end
if t==0
    y=1;
else
    y=0;
end
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=max_row(h)
s=size(h);
v=[];
for k=1:s(1)
    v=[v,row_pic(k,h)];
end
y=index_of(max(v),v);
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=notf(x)
if x==1
    y=0;
else
    y=1;
end
end
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=npv_test(t)
%t is a row in the p matrix (in convert3.m) containing instances of pv's in the string
%here we're converting the matlab expressions of numerals into decimal
%form
r=[];

for i=1:length(t)
if numerical_string_entry(t(i))==1
r=[r t(i)];
end
end

sum=0;
for k=1:length(r)
v=10^(length(r)-k)*(r(k)-48);
sum=sum+v;
end
y=sum;
end



%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=numerical_string_entry(string_element_encoding)
c=0;
for i=48:48+9
    if string_element_encoding==i
        c=c+1;
    end
end
if c==0
    y=0;
else
    y=1;
end
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=row_pic(k,x)

r=[];
s=size(x);
for i=1:s(2)
    if numerical_string_entry(x(k,i))==1
    r=[r x(k,i)];%here we extract numerical entries from the character array
    end
end
sum=0;%here each numerical row is transformed to a unique scalar quantity 
%required to determine the largest numerical entry i.e. largest pv
for i=1:length(r)
sum=sum+(10^(length(r)-i))*(r(i));
end
y=sum;
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=orf(x,z)
if x==1 || z==1
    y=1;
else
    y=0;
end
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=tautology(x)
w=wff(x);
if w(1)==7 && w(length(w)-2)==1
    y='ERROR: the number of left-hand brackets must equal the number of right-hand brackets';
else if w(1)==7 && w(length(w))==1
    y='ERROR: for any pn appearing in the wff, all pk such that 1=

else if w(1)==7 && w(length(w)-1)==1
    y='ERROR: superflous brackets - double check the syntax!';

    else if w(1)==7 && w(length(w)-1)==-1
    y='ERROR: insufficient brackets - double check the syntax!';
        else 

        npvs=log2(length(w)-2);
        %we can easily extract the number of propositional variables from wff(x),
        %since wff spits out a one dimensional array of the value of the wff for
        %each interpretation.
        t=truth_table(npvs);
        counter_model=[];
        if sum(w(1:length(w)-3))==length(w)-3%if wff is all 1's i.e. 1 on every interpretation
           y=1;
        else 
           y=0;
           counter_model=t(min(index_of(0,w)),:);
           %here we give just the nearest countermodel - it's sufficient!
           %however the nearest_zero function can be altered to give all
           %the counterexamples
           counter_model
        end
        end
    end
    end
end
end



%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y= truth_table(nPVs)
%this program generates binary strings required to construct a semantic
%table (table for Propositional Calculus of all interpretations for a given number of PV's) 
%Basically here we generate thruth tables for a given number of PV's.
v=[];
for n=1:nPVs
    for k=1:(2^nPVs)/(2^(n-1))
        for i=(2^(n-1))*(k-1)+1:2^nPVs
            if is_even(k)==0
            v(i,n)=0;
            else
            v(i,n)=1;
            end
        end
    end
end
y=v;
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=valid(x,z) 
conversion=['conf(n_andf([',x,']),',z,')'];
y=tautology(conversion);
end



%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=all_pvs(x)
c=0;
for i=1:length(x)
    if x(i)=='p'
        c=c+1;
    end
end
y=c;
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=bconf(x,z)
if (x==1 && z==1) || (x==0 && z==0)
    y=1;
else
    y=0;
end
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=conf(x,z)
if x==0 || z==1
    y=1;
else
    y=0;
end
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=consistency(x)
w=wff(x);
if w(1)==7 && w(length(w)-2)==1
    y='ERROR: the number of left-hand brackets must equal the number of right-hand brackets';
else if w(1)==7 && w(length(w))==1
    y='ERROR: for any pn appearing in the wff, all pk such that 1=

else if w(1)==7 && w(length(w)-1)==1
    y='ERROR: superflous brackets - double check the syntax!';

    else if w(1)==7 && w(length(w)-1)==-1
    y='ERROR: insufficient brackets - double check the syntax!';
        else 

        npvs=log2(length(w)-2);
        %we can easily extract the number of propositional variables from wff(x),
        %since wff spits out a one dimensional array of the value of the wff for
        %each interpretation.
        t=truth_table(npvs);
        Model=[];
        if sum(w(1:length(w)-3))>0%if wff is all 1's i.e. 1 on every interpretation
           y=1;
           Model=t(min(index_of(1,w)),:)%Here is the model where the set is satisfied - we provide just one,
            %but the nearest_one function can be altered to obtain all the models.
        else 
           y=0;                    
        end
        end
    end
    end
end
end



%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%------------Created by Mariusz Popieluch 2011 prime4567@gmail.com---------
%--------------------------------------------------------------------------
%------------------http://www.mariuszessays.blogspot.com-------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=consistent(x) 
conversion=['n_andf([',x,'])'];
y=consistency(conversion);
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------

function y =convert3(x)
%-------------------------------------------------
%syntax check if the number of brackets is equal
l=0;
r=0;
dd=0;
for i=1:length(x)
    if x(i)==40
        l=l+1;
    end
    if x(i)==41
        r=r+1;
    end
end
if r~=l
    dd=1;%'ERROR: the number of left-hand brackets must equal the number of right-hand brackets'
end

%-------------------------------------------------
%the loop below extracts the pv numerals and for each pv inserts then in
%the p matrix where each pv numeral goes into a seperate row
b=0;
h=0;
for t=1:length(x)%this makes the code clean so any pn is a wff
if x(t)== 'p'
    h=h+1;
end
end
f=0;
for t=1:length(x)%sufficient brackets for the number of functions
if x(t)== 'f'
    f=f+1;
end
end
ee=0;
if 2*r<2 f="" font="">
    ee=-1;%'ERROR: insufficient brackets - double check the syntax!'
else if 2*r>2*f
        ee=1;%'ERROR: superflous brackets - double check the syntax!'
    end
end
if h~=1 && x(length(x))~=41%just taking care of cases without last bracket
    x=[x 41];
    ee=-1;
end
%---------------------------------------------------------------
%here we create a matrix of x length and all_pvs height
siz=all_pvs(x);
p=zeros(siz,length(x));
for k=1:length(x)
for i=1:siz
    p(i,k)='*';
end
end
%----------------------------------------------------------------
% if h==1
%     y=[112 40 118 44 49 41 1 0 0 0];%here we just return the convertend string p(v,1) i.e. representing one pv
% else

for i=1:length(x)%this code extracts all numerial string entries from the wff and inserts them in the rows of p
    if x(i)=='p'
        b=b+1;
       for k=1:length(x)
            if numerical_string_entry(x(i+k))~=0
               p(b,k)=x(i+k);
            else
                break
        end
     end
    end
end

%-------------------------------------------------
%Next we determine the order of the pv's by finding the maximum length of 
%numeral strings in the p matrix.
pdash=zeros(siz,length(p));
for i=1:siz
    for k=1:length(x)
        if numerical_string_entry(p(i,k))==1
            pdash(i,k)=1;
        end
    end
end
pvorder=max(sum(pdash'));
numeralspace=sum(sum(pdash'));%the number of numerical entries in x
%-------------------------------------------------
%conversion proper
s=size(p);
nthpv=0;%n'th row in p corresponding to the n'th pv appearing in x
c=0;%is the number of accumulated entries through conversion i.e. 4 for each pv
lenxdash=length(x)+4*siz;
xdash=zeros(1,lenxdash);
for i=1:length(x)
      if x(i)=='p'
         nthpv=nthpv+1;
         leng=sum(pdash(nthpv,1:s(2)));%number of numerical entries in pdash's i'th row
         g=['p','(','v',',',p(nthpv,1:leng),')'];%replacement string considering each pv i.e. p row
         xdash(i+c:i+c+length(g)-1)=g(1:length(g));%conversion
         c=c+4;%accumulated entries through conversion
      end
end
%---------------------------------------------------
%Here is the code that counts the number of pv's

c=[];
for i=1:s(1)
for j=1:s(1)
if npv_test(p(i,1:s(2)))==npv_test(p(j,1:s(2)))
c=[c 0];
else
c=[c 1];
end
end
end

if sum(c)==0%this implies tht all pv's are identical
    npvs=npv_test(p(1,1:s(2)));%and here we just determine which one it is
else
    max_row_p=max_row(p);%creating a variable so 
npvs=npv_test(p(max_row_p(1),1:s(2)));%we pick one only instead of all the indexes where the maximum pv's appear
end
%---------------------------------------------------
%--------------------------------------------------
%Before we count the number of pv's we need to determine if the syntax is
%correct - this bit of code determines if there are any non sequential
%instances of pv's eg. p1,p2,p4 instead of p3
gg=0;
max_pv=npvs;%npv_test(p(max_row(p),1:s(2)));
for k=1:max_pv-1
    t=0;
    for i=1:s(1)
        if npv_test(p(i,:))== max_pv-k
            t=t+1;
        end
    end
        if t==0
            gg=1;%'ERROR: for any pn appearing in the wff, all pk such that 1
            break
        end
end

%--------------------------------------------------------------------------
empty_xdash=index_of(0,xdash);%this is ok
nonpvx=index_of_not_general('p',x);
xdash(empty_xdash)=x(nonpvx);
y=[xdash,npvs,dd,ee,gg];
end

%this is the PROPER EXECUTION LINE, just xdash will have to be
%transformed to char(xdash) in the program treating it as a wff string.
%eg. v=convert3('the actual wff string')
%x=char(v(1:length(v)-1); y=v(length(v)); where x is the wff and y is the
%number of pv's in that wff
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------

function y=index_of(x,z)
p=[];
 for i=1:length(z)
    if z(i)==x
        p=[p i];
    end
end
y=p;
end
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
function y=index_of_not_general(x,z)
p=[];
%for k=1:length(x)
    for i=1:length(z)
      if z(i)~=x && numerical_string_entry(z(i))==0
        p=[p i];
      end
    end
%end
y=p;
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------

function y=row_pic(k,x)

r=[];
s=size(x);
for i=1:s(2)
    if numerical_string_entry(x(k,i))==1
    r=[r x(k,i)];%here we extract numerical entries from the character array
    end
end
sum=0;%here each numerical row is transformed to a unique scalar quantity 
%required to determine the largest numerical entry i.e. largest pv
for i=1:length(r)
sum=sum+(10^(length(r)-i))*(r(i));
end
y=sum;
end

%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------


Monday, April 25, 2011

Number Theory 2

In the previous post we derived an interesting (although rather basic) result from the fact that:

xn + xn+m = 2k

For n∊ℤ+, k,x∊ℤ, and m∊ℕ. That result entails: xn xn+m (mod 2). Can we get a similar result for mod 3? That is, what are the m,n∊ℤ such that xn xm (mod 3) ?
It turns out that m,n just need to be even. 
Proposition 2   For n,m∊ℕ, x∊ℤ
x2n x2m (mod 3)
Proof
We have three cases: x=3k, x=3k+1 and x=3k+2  k∊ℤ. The first two are identical to mod 2 cases proven in the previous post i.e. ( 3k )n, and  ( 3k+1 )n factorize to be multiples of 3 and multiples of 3, +1 respectively. All that remains to show is that ( 3k+2 )n = 3m+k,m∊ℤ, or more precisely what restrictions need to be imposed on n for this equality to hold.
By The Binomial Theorem all the terms except the constant factorize as multiples of 3, but we're left with a 2n constant term at the end. We want it to have the form 3m+2, so the first term can be factorized and the second to be the reminder.
Consider 2n-2+2, so the question remains to find n such that 3|2n-2 = 2( 2n-1-1 ). 
Note that if 3|2n-1-1then 3| 2( 2n-1-1 ). The following lemma gives us the required result:

Lemma: 3| 22n-1 for n∊ℕ
Proof by induction on n:
22n-1 = 4n-1
Base case: 40-1 = 1-1 = 0 = 3(0)
Now suppose that if 3|4k-1 implies 3|4k+1-1 for arbitrary k∊ℕ then 3|4n-1 ∀n∊ℕ.
In other words is  4k+1-1 divisible by 3 given that 4k-1 is?
4k+1-1 =  4k+1- 4+3 = 4( 4k-1 ) +3 = 4(3j) +3 (by inductive hypothesis) = 3( 4j +1 ) j∊ℤ
Hence 3|4n-1for ∀n∊ℕ q.e.d. 
Incidently this is also a result about Mersenne Numbers. It says that at least half of the Mersenne Numbers are divisible by 3.

Now returning to our original discussion the lemma gives us m such that 3| 2( 2m-1 ), namely m needs to be even. Since no restrictions on parity of m were necessary in the 3k, and 3k+1 cases, it follows that
xn xm (mod 3) iff n and m are even. Or just, for any n,m ∊ℕ,  x2n x2m (mod 3), as required. 

Corollary 1.1
Propositions 1 and 2 jointly give n, m > 0, |x| > 2:
x2n x2m (mod 6)


Example. This result guarantees that  |x| > 2, a∊ℤ , i > 0, and ∀n∊ℕ