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)

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 ...
0
votes
1answer
16 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 ...
-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 ...
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 ...
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
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
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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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
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
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 ...
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
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 ...
-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
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))$ $ ...
-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
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 ...
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 ... ...
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 ...
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
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\\ ...
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.
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 ...
0
votes
0answers
13 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
48 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
39 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
26 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
32 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
109 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
31 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
27 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
25 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
39 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
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 ...
1
vote
3answers
78 views

Propositional Logic- Prove sentences (a) and (b) entail (c)

I'm given three sentences: (a) If Frodo destroys the ring, then the world will be saved. (b) Gollum stole the ring from Frodo or Frodo destroyed the ring. (c) The world will be saved or Gollum stole ...
0
votes
1answer
17 views

Reducing propositional logic statements

I am having some trouble with reducing some propositional logic statements. The first one is as follows: $\neg(P \lor Q) \lor \neg (P \lor \neg Q)$. I used deMorgan's law to change this to: ...
0
votes
1answer
34 views

Verification of Lindenbaum's Lemma proof for the Mendelson system and a question of maximally consistent sets.

In this proof I will use Mendelson's axiom system (the one in this book). Question 1: Could someone check my work? I feel some parts are a bit hard to see/read, but I think the general idea ...