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
1answer
72 views

proof that $\{\rightarrow, \land \}$ is not a complete set of logical connectives

I need some help to prove that the set $\{\rightarrow, \land \}$ of logical connectives is not a complete set. can someone help me to understand what should I do? thanks!
0
votes
1answer
23 views

Counterexamples of existentially quantified statements

I just realized I have a serious problem in properly seeing the logical structure that involves counterexamples. Here there is an example: Proposition F: Assume $P$. Then, there is a function $f \...
0
votes
1answer
34 views

propositional calculus problem, is this right proof? [duplicate]

I would like to confirm my proof.
0
votes
2answers
34 views

propositional calculus problem, how to prove this right or wrong?

$A$$\rightarrow$$(B$ $\vee$ $C$ ) , $B$ $\rightarrow$ $C$ $\vDash$ $A$ $\rightarrow$ $D$ I think it's wrong but I have no idea how to prove.
0
votes
1answer
16 views

$\Sigma$ is maximally satisfiable $\iff$ there exists $M$ such that $\Sigma=\{\alpha \mid M\vDash \alpha\}$

A set of formulas $\Sigma$ is maximally satisfiable $\iff$ there exists $M$ such that $\Sigma=\{\alpha \mid M\vDash \alpha\}$. I have easily proved that if $\Sigma$ is maximally satisfiable than $\...
0
votes
1answer
38 views

Is this a valid propositional natural deduction proof?

I'm new to logic and I tried to solve an exercise. Since there isn't a given answer, I'd appreciate an indication of whether this is correct ...
1
vote
1answer
22 views

logic: derive a formula using laws

Let's say I have the following formula: $$(A\wedge\neg C)\vee(B\wedge C)\vee(A\wedge B).\tag{1}$$ It is easy to show following: $$(A\wedge\neg C)\vee(B\wedge C)\vee(A\wedge B)\Leftrightarrow (A\wedge\...
1
vote
1answer
57 views

Truth table and induction

It is true that every truth table can be represented by some wff built using only the connectives $\neg, \implies$ and $\iff$ - let's call it "negation-arrow-wff" for convenience. I want to be able to ...
0
votes
2answers
34 views

Decide if $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology

How can I show that $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology? I tried to apply the implication rule $(p\Rightarrow q)\equiv (\neg p\vee q)$ but it doesn't ...
0
votes
0answers
20 views

Show that if X implies Y is valid, then X is unsatisfiable or Y is valid

How can I show that if X and Y are two formulas with no propositional variables in common, and (X ⇒ Y) is valid, then either X is unsatisfiable or Y is valid (or both). I know that (X ⇒ Y) is false ...
0
votes
1answer
70 views

Formal deduction proof of predicates

I am trying to proof equality is transitive, that is, $\emptyset \vdash \forall x \forall y \forall z ((x=y) \land (y=z) \to(x=z))$ using formal deduction (17 rules) and also other rules (ex. To ...
1
vote
1answer
53 views

HPC: Prove that $\vdash A\to \lnot\lnot A$

Prove that $\vdash A\to \lnot\lnot A$ By Deduction Rule we know that it is sufficient to show that ${A}\vdash \lnot\lnot A$ I am also familiar with the formula: $\lnot A \vdash (A\to B)$. So if I ...
1
vote
2answers
65 views

Modus Tollens Proof

I came across the following proof in the book Logic, by Paul Tomassi: (P & Q) → ~R : R → (P → ~Q) According to the author, the proof should be a simple application of modus tollens. The following ...
2
votes
1answer
27 views

property about truth tables

Is the question "show that any truth table is same as the truth table for some wff built from $\neg,\implies,\iff$ only" the same as asking show that any wff is logically equivalent to some wff built ...
0
votes
2answers
73 views

Writing proposition with connectives and laws of logic

Question 1): Pei Ann has been dealt two cards from a standard 52 card deck. She holds one in her left hand and one in her right. Let $p$ be the proposition "The card in Pei Ann's left hand is an ace"....
0
votes
1answer
25 views

Converting formula from CNF to DNF

How do i convert this formula from CNF to DNF? $(¬a \vee b) ∧ (¬b ∨ c) ∧ (¬a ∨ ¬c)$ $(¬a ∨ b) ∧ (¬b ∨ c) ∧ ¬(a ∧ c)$ DeMorgan ?
0
votes
1answer
34 views

Constructing the $\wedge$ logical connectives using $¬$ and $\leftrightarrow$

I am trying to show that if $p, q$ are distinct propositional variables, then there is no propositional formula $\phi$ such that the only connectives are $\leftrightarrow$ and $¬$ that is ...
0
votes
4answers
44 views

equivalent to $A \to (C \leftrightarrow D)$

I am somewhat confused while reading a paper. Are these two statements equivalent? $ A \wedge B \to (C \leftrightarrow D)$ $ [(A \wedge B \wedge C) \to D] \land [(A \wedge B \wedge D) \to C]$ I ...
0
votes
1answer
30 views

Propositional Logic; Im lost!

The proof I have to solve is: $$\lnot Z,~ \bigg((\lnot Z \lor S) \lor T\bigg) \implies L \vdash L \lor T$$ Basically I have tried to work backwards trying to prove the contradiction of $L \lor T$ ...
0
votes
1answer
29 views

Propositions ,Logic

John made the following statements: 1.I love Lucy 2.If i love Lucy then i love Vivian. Given that john either told the truth or lied in both cases.Determine whether John really loves Lucy.What that ...
1
vote
1answer
77 views

“This statement is false” - Propositional Logic

In a text I am reading, the section on Propositional Logic says that a proposition is a statement that is either true or false, but not both true and false. Also, from this lecture online, the ...
0
votes
1answer
68 views

Is mathematical induction the only known example of a higher-order logic?

Mathematical induction is one well known and widely cited example of a second-order logic. I was wondering whether there are other examples of arguments involving higher-order logic in any branch of ...
0
votes
1answer
23 views

Formal proof of predicates

I need to provide a formal proof of the following argument: Premise: $\exists x[P(X)\land\forall y(Q(y) \to \lnot R(x,y))]$ Premise: $\forall x[P(x) \to \forall y(S(y) \to R(x,y))]$ Conclusion: $\...
1
vote
3answers
198 views

“This statement is false.” [duplicate]

In propositional logic, a proposition is a statement that is either true or false, but not both. In a text I am reading and in many others, "this statement is false" is not considered a proposition. ...
1
vote
1answer
41 views

How is the first premise true if variable $B$ is true?

Hi this is my second time on here so I am not quite able with the tools yet but I will try and do my best. I am currently studying How to Prove It by Daniel J. Velleman page [19] On page 19 number 2 ...
4
votes
4answers
168 views

Iff Interpretation

I understand that (1) "$A$ if and only if $B$" ($A\iff B)$ means that (2) "$A$ implies $B$ and $B$ implies $A$" $(A\implies B)\land (B\implies A)$. The phrase "$A$ if and only if $B$" sounds as ...
1
vote
1answer
39 views

Looking for in depth material on a formal propositional calculus using only the NAND connective

I am looking for secondary literature on a formal propositional calculus which has the NAND connective as its sole connective. I am coming upon many pages which briefly state that Nicod had shown ...
2
votes
3answers
102 views

Understanding iff [duplicate]

I'm having difficulty understanding why it is appropriate to use if and only if, something I thought I had a firm grasp on. From Lara Alcock's book, How to Study as a Mathematics Major: ...
1
vote
1answer
40 views

Should this be conditional or biconditional?

You can access Internet from campus only if you are a CS major or you are not a freshman How can the above English sentence be translated into a logical expression? I think this is biconditional ...
3
votes
1answer
94 views

Why are Duals of Two Equivalent compound propositions Equivalent?

I know that if we have two equivalent propositions p and q then p* and q* will also be equivalent where p* and q* are duals of p and q respectively. I am looking for some explanation to why duals of ...
0
votes
2answers
45 views

why not include another assumption within natural deduction

question: prove $p → q \vdash ¬q → ¬p$ is valid. The answer is: $1. p → q~~~~\textsf{premise}$ $2. ¬q~~~~~\textsf{assumption}$ $3. ¬p~~~~~\textsf{MT }1,2$ $4. ¬q → ¬p~~~~~→\textsf{...
2
votes
2answers
78 views

Ideas for a history of math paper (with an emphasis on the mathematics), having to do with 19/20th century logic?

So I'm currently taking a history of math course and I need to write a 15 page paper in place of my final. It's a 400 level course (high undergrad) so the paper needs to have emphasis on the ...
12
votes
7answers
3k views

Show that (p ∧ q) → (p ∨ q) is a tautology?

I am having a little trouble understanding proofs without truth tables particularly when it comes to → Here is a problem I am confused with: Show that (p ∧ q) → (p ∨ q) is a tautology The first ...
0
votes
1answer
27 views

Help understanding $P\land Q$ derivation in implicational propositional calculus?

According to its formulation, the implicational propositional calculus uses implication equipped with a tautologically false proposition $F$ to achieve soundness. Thus, consider the following ...
0
votes
2answers
29 views

formulating English sentences to logic

Consider the following sentences "We will play outside tomorrow, if there will be no rain" "We will play outside tomorrow, only if there will be no rain" Let's denote: $A$ = "play outside ...
1
vote
1answer
33 views

Help understanding the difference between imperative and logical conditionals?

How would you define a truth set $A$: for all $x \in B$ that satisfies $Q(x)$ where $B$ is another truth set that satisfies $P(x)$? I'm trying to formalize the natural intuition of if-then as distinct ...
0
votes
1answer
123 views

Equivalence classes under logical equivalence by 13 valuations

Let L be the set of 5 propositional variables. Under the equivalence relation given by logical equivalence, how many equivalence classes of propositional terms are given the value TRUE by 13 ...
0
votes
1answer
20 views

Formulas of propositional logic, two sets and refutation.

Let $\alpha$ and $\beta$ be two formulas of propositional logic and set $S_\alpha$ and $S_\beta$ be the sets of clauses representing $\neg \alpha$ and $\neg \beta$, respectively. Show that if $S_\...
0
votes
3answers
33 views

Logical Equivalence of two propositions [closed]

Are the following two propositions logically equivalent? $p \rightarrow (\neg q \land r)$ and $\neg p \lor \neg(r \rightarrow q) $ For this one, I'm pretty sure that they are not equivalent ...
0
votes
1answer
16 views

Proving the negation of conditional via propositional calculus

https://www.dropbox.com/s/2dpk7fvae668phn/Screenshot%202016-03-03%2018.13.42.png?dl=0 Hi, I'm trying to prove the negation of a conditional. Basically, prove ¬(α → b) is equivalent to α ∧ ¬b. I've ...
6
votes
3answers
928 views

Proof of (P → Q) from ¬P?

I'm trying to figure out how to prove P → Q from just ¬P. I can deduce it using informal logic. Since the only way a conditional is False is in the case of T → F, if P is False, P → Q must always be ...
0
votes
1answer
31 views

Resaults of conditional statments

Is there a way to represent multiple conditional statements in a truth table and find the results of them: e.g., if person $A$ passes the exam, then person $B$ re-enters the exam. if person $A$ re-...
1
vote
0answers
61 views

how to prove the following formula via natural deductions $a ∧ ¬a \vdash b ∧ ¬b$

Hi I am trying to prove the following formula via natural deduction and this is what I have so far. I am not sure however if this is entirely correct. If I could get some verification and be pointed ...
-1
votes
1answer
37 views

Tautology example [closed]

How to verify if this logical statement is a tautology? AB+BCD+AC=NOT(AB+AC) I have seen all the posibilities but I am not sure that is tautology. And I have to solve it and to do all the ...
1
vote
0answers
48 views

Generating all logic propositions

I'm looking for a way of generating all logic propositions (propositional calculus) in an "algorithmic" way. The equivalence is symbolic, so $\neg\neg a \neq a$ and $\neg a \lor b \neq a \implies b$, ...
0
votes
1answer
29 views

Prove Tautology

Can you please prove the equation (~pVr)^(pVq)->(qVr) without using truth table. I have tried and ended up half way ~[(~pVr)^(pVq)]V(qVr) ~(~pVr)V~(pVq)V(qVr) (p^~r)V(~p^~q)VqVr (p^~r)VrV(~p^~q)Vq
0
votes
1answer
24 views

How to specify the corresponding line of a truth table in a formula?

How to specify the corresponding line of a truth table in a formula: $$p \to (\neg q \lor (q \to p))$$ $p$ evaluates to $F$ and $q$ evaluates to $T$. I want to know the method followed to find this....
2
votes
1answer
30 views

How to handle degrees (numerical attributes) in logic? How to model “quantitative changes lead to qualitative changes”?

I am using logics (propositional, predicate, modal) to model one domain, but there are variables that have non-boolean domains, these variables are degrees (it is sufficient that they are degrees, ...
1
vote
2answers
67 views

What will the declarative sentence No shoes, no shirt, no service be in propositional logic?

I need to write the following declarative sentence in propositional logic. No shoes, no shirt, no service. My solution is: ~p,~q, ~r , is it correct or do i need to use implication -> instead
2
votes
1answer
55 views

All hill-stations have a lake. Ooty has two lakes?

All hill-stations have a lake. Ooty has two lakes. Which of the statement(s) below is/are logically valid and can be inferred from the above sentences? $(i)$ Ooty is not a hill-station. $(ii)$ No ...