Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

1
vote
2answers
2k views

Proving De Morgan's Law with Natural Deduction

Here is my attempt, but I'm really not sure if I've done it right; as I'm just about getting the hang of Natural Deduction technique. Have I done it correctly? If not, where did I make errors and ...
2
votes
3answers
48 views

$a \Rightarrow b$, $b \Rightarrow c$, $c \Rightarrow d$, $d \Rightarrow a$. Argue that any two of these statements are logically equivalent.

Suppose a,b,c and d are statements such that $a \Rightarrow b$, $b \Rightarrow c$, $c \Rightarrow d$, $d \Rightarrow a$. Argue that any two of these statements are logically equivalent. Hey, Im ...
0
votes
1answer
29 views

Lambda Calculus Proof: or false (not true) Evaluates to False, using lazy evaluation, Help!

I am trying to learn lambda calculus, and I am currently tackling a few boolean logic questions. I have gotten to one that I am stuck on, and I am looking for a little help proceding. I need to ...
5
votes
1answer
1k views

Online tools for checking validity of classical, intuitionistic, … logic formulas?

What online tools are available, where one can enter a formula of (first order) propositional or predicate logic, and have it check whether it is valid classically, intuitionistically, or even ...
0
votes
1answer
17 views

On the functional-completeness of the sheffer stroke

I have seen functional-completeness (in regards to boolean functions) defined as: A set X of truth-functions (of 2-valued logic) is functionally complete if and only if for each of the five ...
0
votes
2answers
364 views

Prove using a proof sequence and justify each step

Prove using a proof sequence that the argument is valid [ A --> (B ∨ C) ] ∧ B' ∧ C' --> A' I'm having some trouble figuring the proof out here. Here is what I have so far. Is this on the right ...
1
vote
1answer
48 views

Propositonal equivalence and compound proposition

Without using truth tables, show that the statements ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ and ...
-2
votes
1answer
37 views

Propositional-Calculus/ Set Theory Proof using Identities [on hold]

$$(\sim P\,\lor \sim Q)\equiv (Q\to (\sim P\,\lor\sim Q))\land ((\sim P\,\lor \sim Q)\to Q) $$ Can someone demonstrate the identity proof here? I've been trying to figure this out, but with no ...
0
votes
1answer
51 views

prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$

how do I prove the following using Natural Deduction ? $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$ My current approach: So instead of proving $(P \rightarrow R) ...
1
vote
1answer
40 views

Why is this predicate false?

I am stumped at my professor's answer to this predicate logic. all x and y are natural numbers. ∃y∃x(x >= y) I think it is true, since there is a pair ...
0
votes
1answer
38 views

prove using natural deduction $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ [duplicate]

so I ran into some trouble proving the following: $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ My approach thus far: Honestly I'm really stuck. So basically my ...
1
vote
1answer
22 views

How can I show that an argument or proposition is valid through logic proof sequence?

I know the logic of proof sequence as I solved many proof problems, I now have one that has been taken my attention for a couple of days and as easy as it may look, I don't seem able to simplify the ...
1
vote
4answers
35 views

How can this inverse of conditional statement be equivalent?

"A positive integer is a prime only if it has no divisors other than one and itself." The inverse of this conditional statement is : " A positive integer is not prime if it has divisors other than one ...
1
vote
0answers
16 views

How to solve this equation using semantic equivlence

Hi I am trying to workout the solution to this propositional logic formula using the below semantic equivalence formula but I am stuck. Could someone please help me out. These are the rules ...
0
votes
1answer
61 views

Is it possible to create a software to find formal proofs?

Let's say I have a Hilbert style system, with a few axioms and rules of inference, and I want to find a proof for some formula $\varphi$, is it possible to create an algorithm that would find a proof ...
0
votes
4answers
2k views

Prove that $\vdash p \lor \lnot p$ is true using natural deduction

I'm trying to prove that $p \lor \lnot p$ is true using natural deduction. I want to do this without using any premises. As it's done in a second using a truth table and because it is so intuitive, I ...
0
votes
1answer
27 views

natural deduction problem using the connective not

I am having problems understanding how the connective not works in natural deduction. We were given the below example but I cannot workout how the lecturer got the values in table. If someone could ...
1
vote
2answers
49 views

Proof for ∨ distributing over →

I'm am stuggling to prove the following: x ∨ ( y → z ) ≡ ( x ∨ y ) → ( x ∨ z ) After making a truth table, I know that disjunction distributes over implication but I am failing to prove the above ...
0
votes
1answer
27 views

How to use natural deduction for introducing implication

I am doing some propositional logic and we learned about the natural deduction rule. Everything was going fine until the rule of introducing implication arose. I am slightly confused as to how it ...
1
vote
1answer
40 views

Tautological Proof Help

I've been having some trouble with proving or disproving tautologies. I am very new to proofs and am hoping I am on the right track. The question asks to show that: If ψ → φ is a ...
1
vote
1answer
37 views

Help understanding a particular proof of the compactness theorem for Propositional Calculus.

I've reading through this proof, I don't understand the last part: the claim $\tau \models \Sigma$. Note: I'll use $AP(\varphi)$ and $\text{Var}(\varphi)$ interchangeably, to mean the variables that ...
0
votes
0answers
20 views

Where can i learn about propositions, predicates and constructing a truth table?

I need help on where i can learn about propositions, predicates and constructing a truth table and be able to answer questions like this; Represent a statement using propositions, construct a truth ...
1
vote
2answers
31 views

Does a statement need to be a biconditional statement to prove by the contrapositive

I am trying to write a proof and was wondering if a then b, the converse if b then a might not be true. This leads me to wonder if the statement needs to be an if and only if statement if it can be ...
0
votes
0answers
20 views

Are these two formulas theorems in the mendelson system of prop. calc? [closed]

Are $$((a\rightarrow b)\rightarrow (\neg\neg a \rightarrow \neg \neg b))$$ and $$((a\rightarrow \neg b) \rightarrow (\neg \neg a \rightarrow \neg b))$$ theorems in the mendelson system? I really ...
1
vote
2answers
29 views

How can I negate this conditional statement? [closed]

The conditional statement is: If today is February 1, then tomorrow is Ground Hog's Day. I need to negate this but I am confused. Would it just be If today is not February 1, then tomorrow is not ...
4
votes
5answers
535 views

Is the propositional set countably infinite?

Recently I'm learning logic. Here is the definition from the book "Logic For Computer Science": A countable set $PS$ of proposition symbols: $p_0,p_1,\dots$ The set $\text{Prop}$. propositions is the ...
2
votes
1answer
32 views

Verification of proof of propositional logic

I made a proof for the following theorem. But I'm not completely certain that it's fully correct. Suppose $\phi$ is a propositional formula and that the two evaluations $v$ and $w$ are equal for ...
0
votes
1answer
50 views

Propositional function and Rule of Inference

I'm reading Cohen's 'Set theory and Continuum Hypothesis'. In the book, propositional function is defined as follows: If $A$ is a variable letter then $A$ is a propositional function. If $A$ and $B$ ...
1
vote
1answer
18 views

Do the inputs to a boolean-function need to be boolean variables?

That is, say we had the following: define a set, $A$, as: $A = \{x,y,z\}$ If we had a function which only takes the elements of $A$ as its inputs, and returns "true" if $x$ is an input and false if ...
51
votes
19answers
6k views

In classical logic, why is $(p\Rightarrow q)$ True if both $p$ and $q$ are False?

I am studying entailment in classical first-order logic. The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: $$\begin{array}{|c|c|c|} ...
0
votes
1answer
54 views

Finding a truth function

I wanted to find a truth function $f$ if it exists that make the formula below true: $((p\to \lnot(q \oplus \lnot p)) \to (\lnot r \oplus (q \to p)))$ Where the $\oplus$ operator is defined as: ...
1
vote
1answer
846 views

Propisitional logic exam questions and answers

I'm going over exam questions, since my exam is hours away. I'd be extremely grateful if you could check out my answers and evaluate them. Hopefully you guys can see the truth table. Also, i have ...
2
votes
1answer
60 views

How to convert to disjunctive normal form?

The formula is: $\lnot((s \lor \lnot p) \land (q \land r))$ and what I've done so far is this: $\lnot(s\lor\lnot p) \lor\lnot(q\land r) $ $(\lnot s\land p) \lor (\lnot q\lor\lnot r)$ After this ...
1
vote
1answer
189 views

Propositional logic truth tables

For the exam that I am taking, propositional always comes up with identical questions. These include writing a sentences in propositional logic, which I can do. But also drawing a truth table for ...
1
vote
1answer
27 views

How to read predicate formulas

I have just started learning about predicate logic and am having some trouble in figuring out how to actually read the formula as as a sentence. ...
0
votes
2answers
49 views

Method of Proving Soundness of Propositional Logic

I am currently taking an introductory course to mathematical logic. We have started with propositional logic and today introduced the Gentzen style proof calculus. In order to prove that the soundness ...
1
vote
1answer
76 views

If a formula $φ$ contains at most one occurrence of any sentence letter, then $φ$ is not a tautology.

If a formula $φ$ contains at most one occurrence of any sentence letter, then $φ$ is not a tautology. The only connectives in my system are $→$ and $¬$. I think I should attempt this by induction on ...
1
vote
2answers
38 views

Deductive Proof - Justify each step with law or inference rule

My Professor gave me the following: a) If $P \to Q, \neg R \to \neg Q$, and $P$ then prove $R$. b) If $P \to (Q\wedge R)$ and $\neg R\wedge Q$ then prove $\neg P$. I understand how to do ...
0
votes
1answer
20 views

Need some assistance converting to conjunctive normal form

I've been asked to convert a couple formulas to CNF. I've tried them several times but I always get stuck at the same point. They are as follows: $(P \to (Q \to R)) \to (P \to (R \to Q))$ $ ...
2
votes
1answer
531 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
-1
votes
0answers
10 views

Solve the Boolean algbraic expression by using DEmorgan's law in lex and yacc?

1 . Can anyone told me that how to solve Boolean algebraic expression using DE morgan's law in lex and yacc. example:- my expression is Y = ((!A||!B)&&(!C||!D||!E)||!F)&&!G after ...
0
votes
2answers
61 views

Natural deduction, Proof $\vdash$ $P\Rightarrow(Q\Rightarrow P)$

So I have a question regarding natural deduction, are we allowed to "copy" our previous assumption inside a new assumption. I will use an example to illustrate. $\vdash$ $P\Rightarrow(Q\Rightarrow ...
-1
votes
1answer
34 views

prove that $\vdash (P \Rightarrow Q) \lor (Q \Rightarrow P)$

I'm just starting out in natural deduction. So I have a question now how to prove the following. Prove that $\vdash (P \Rightarrow Q) \lor (Q \Rightarrow P)$ I'm finding this rather difficult cause, ...
0
votes
2answers
68 views

Can anything be the logical consequence of an always false statement? For eg: $p \wedge \neg p$

$p \wedge \neg p$ is never true, does that mean that any statement can be it's logical consequence?
0
votes
1answer
45 views

Confused about proof by contradition

In proof by contradiction, I can understand how it works when the hypothesis leads to a clearly false proposition. e.g., if we want to prove $P$, we assume $\neg P$ and show that $\neg P \implies ... ...
1
vote
2answers
39 views

how to prove the following formula true using semantic equivalences

Hi I am trying to prove the following the formula and this is what I have so far false ∨ p ≡ p This is what I have do so far ...
0
votes
1answer
35 views

How to solve this propositional logic propblems using the following rules.

Okay so I have the following problem, which I need to solve without using truth tables. This is the formula p ∧ (¬p ∨ q) ≡ p ∧ q and these are the semantic ...
0
votes
2answers
27 views

How can I prove the following formula using semantic equivalences

Hi I am trying to prove the following formula using semantic equivalences $$(p \land q) \to r \;\equiv\; p \to (q \to r )$$ I am thinking maybe to use the implication rule but I am note sure.
0
votes
1answer
29 views

Proving inadequacy given a set of connectives

Let $\oplus$ be a binary connective defined by the truth table: $\begin{array} {|r|r|} \hline p &q & p \oplus q\\ \hline 0 &0 &0\\ \hline 0 &1 &1\\ \hline 1 &0 &1\\ ...
1
vote
3answers
47 views

Verify if Propositions hold or not

I want to show wether or not these two propositions hold or not. The first one is that $$\forall x\exists y(xy>0\implies y>0)$$ For this one I noticed that hen $y=0$ it doesn’t hold. But I’m ...