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
55 views

How to demonstrate this tautology using equivalences?

I have this tautology $(P \wedge (P \rightarrow Q) \wedge (Q \rightarrow R)) \rightarrow R$ I couldnt prove it by using equivalences. Using Definition of implication and then using negative ...
0
votes
2answers
97 views

Natural deduction proof / Formal proof : Complicated conclusion with no premise

Find a formal proof for the following: $\vdash [(\neg p \land r)\rightarrow (q \lor s )]\longrightarrow[(r\rightarrow p)\lor(\neg s \rightarrow q)]$ As you can see. No premise to use. We have to use ...
0
votes
1answer
19 views

Propositional variables in semantic equivalence

I'm learning the semantic equivalence rules/laws in propositional logic, but I'm confused by what the propositional variables in the rules are supposed to represent. For example, the associative ...
0
votes
1answer
43 views

Resolution calculus converting into set of clauses

Here is $T$: $a \lor \neg b$ $\neg a \lor (c \land d)$ $b$ I am suppose to use resolution calculus to prove that $T \models d \land b$ holds. As in the first step, we translate $T$ ...
0
votes
0answers
33 views

Is (A v C) v B in conjunctive normal form?

I need T to be a set of clauses in conjunctive normal form. T = { (¬A ^ ¬C) → B } T = { ¬(¬A ^ ¬C) v B } T = { (A v C) v B } I 'simplified' it to T = { (A v C) v B }, is it in CNF? ...
2
votes
3answers
110 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 ...
1
vote
1answer
42 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 ...
0
votes
1answer
40 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 ...
-3
votes
1answer
49 views

Propositional-Calculus/ Set Theory Proof using Identities [closed]

$$(\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 avail....
1
vote
1answer
45 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 $(...
-1
votes
1answer
55 views

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

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
votes
1answer
69 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
36 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
50 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
32 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
70 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
1answer
40 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 ...
0
votes
0answers
21 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
32 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 ...
1
vote
1answer
42 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 ...
0
votes
1answer
37 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

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
2answers
34 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 ...
1
vote
1answer
22 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 $...
1
vote
1answer
39 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
1answer
60 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
179 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 ...
0
votes
2answers
152 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
2answers
163 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
26 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))$ $ \...
-1
votes
1answer
41 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, ...
-1
votes
2answers
212 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 P)$...
0
votes
2answers
214 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
184 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 ... \...
0
votes
1answer
43 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 ...
1
vote
2answers
51 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
46 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\\ \...
0
votes
2answers
40 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.
1
vote
3answers
52 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 ...
0
votes
0answers
14 views

Find algebraic normal form that's derived from 2 other ANF

I have to find the ANF of a function $h$ where $h = f \star g$ where $x \star y := x \wedge \neg y$. $f$ and $g$ are given functions. They are $f(x, y, z) = y \oplus x \oplus xy \oplus zy \oplus zx \...
0
votes
1answer
54 views

Tarski's semantic conception of truth and logic

Tarski's semantic conception of truth states: $X$ is true iff p (where $p$ is a sentence, and $X$ is the name of the sentence $p$ to which the truth predicate applies). However, in logic, to express ...
1
vote
1answer
41 views

Proof of Why or Why Not some equivalence holds

How do I prove that this equivalence $$\lnot\exists x\,\forall y\,(P(x)\Rightarrow\lnot Q(x,y))\equiv \forall x\,\exists y\,(P(x)\land Q(x,y))$$ holds or not? I remember that $A\implies B\equiv\lnot ...
0
votes
2answers
28 views

I cannot figure out what this question means with the semantic turnstile

Hi I have recently started studying propositional logic and am finally understanding the truth tables and how to use them. I came across this formula which is confusing me. Use truth tables to ...
0
votes
1answer
55 views

DNF simplification

I am currently learning about propositions and logical equivalences in a mathematics course I'm taking at university. I'm having trouble understanding how to simplify DNF Formulas. I was given a truth ...
0
votes
0answers
113 views

Is the establishment of the validity of this argument correct?

I am trying to show that the following argument is valid. There is an email that is sent but it is not saved in the inbox. All emails are saved in the inbox or the inbox is full. If the inbox is ...
0
votes
1answer
35 views

Propositional Equivalence

Are the following two propositions equivalent? p IMPLIES (q IMPLIES r) p IMPLIES (q AND r) From what I can tell, using the logical equivalences, this should be false, correct? p ...
0
votes
1answer
30 views

which of the following are valid propositions?

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE? 1.((∀x(P(x) ∨ Q(x)))) ⟹ ((∀xP(x)) ∨ (∀xQ(x))) 2.(∀x(P (x) ⟹ Q (x))) ⟹ ((∀xP(x)) ⟹ (∀xQ(x))) 3.(∀x(P(x)) ⟹...
0
votes
1answer
37 views

Propositional Logic - Resolution Strategies

I need help understanding these resolution strategies. 1) Set of support 2) Linear input Let's assume $\mathcal{S} = \{ C_1, ... ,C_n\}$ is our set of clauses. and we want to derive / prove ...
0
votes
1answer
46 views

Proof strategy for propositional logic algorithm

I have to proof the following theorem: Proof that $\eta_1 \vee \eta_2 \equiv DISTR(\eta_1, \eta_2)$. The algorithm DISTR($\eta_1, \eta_2$) is the following: Now I want to use induction to ...
2
votes
1answer
33 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 ...