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)

0
votes
0answers
33 views

Create the following wffs(axiom rules for domain) for the domain of lists over alphabet A

Recall that in the domain of Lists over Alphabets, the function cons(a,x) where a is an element in an alphabet and x is a list, produces a new list with a at the beginning of L. The predicate Last(x,...
0
votes
1answer
31 views

proof verification for natural deduction

Could someone please let me know if I got the following natural deduction correct for the following formula ...
3
votes
0answers
53 views

How many ternary functionally complete connectives are there?

Today I was reading up once more on some of the nice results regarding functional completeness, notably Post's celebrated classification theorem with the 5 classes that need to be avoided. (See this ...
0
votes
1answer
10 views

Conjunctive Normal Form (CNF) of a propositional formula

These are my notes for Discrete Math. I'm having trouble understanding how to convert the given formulae at the end into CNF. The example seems to have skipped the steps and jumped straight to the ...
0
votes
2answers
51 views

$P ⇒ (Q ∨ S)$ , how can I prove $Q$?

I'm asking this in the context of a logical programming language similar to Prolog. Say I have the rule $P ⇒ (Q ∨ S)$ . How would I go about proving the truth value of $Q$, assuming I know the ...
1
vote
2answers
59 views

Can an open statement be a tautology?

A tautology is a statement which is true by dint only of the logical connectives contained therein. My question is about a statement which contains an unquantified variable. For example: P: ($x$ ...
1
vote
1answer
24 views

Associativity? Can this be applied here?

As the Associativity law says that (A ∧ B) ∧ C ≡ (A ∧ C) ∧ B, can I do something like this? (A ∧ ¬B) ∨ (B ∧ ¬A) ≡ (A ∧ ¬A) ∨ (B ∧ ¬B) I am new with logic and I still don't get this basic principles....
0
votes
1answer
27 views

Set theory statements vs. propositional statements

I was wondering if statements that hold in general in set theory, such as De Morgan's Laws, always hold in propositional logic as well. If not, what are some examples of such statements that in the ...
0
votes
2answers
37 views

Formal logic proof verification

I am trying to prove the following sequent formally. $$P, (P \land Q)\Rightarrow \sim R \vdash R\Rightarrow \sim Q$$ I have come up with the following formal proof, but I am not completely sure if ...
1
vote
1answer
46 views

A faster way of proving that a 'theorem' (logic) is true.

Suppose I want to prove that the following is a theorem. $$\left [ \left ( P \vee Q \right ) \Rightarrow R \right ] \Rightarrow \left [ \left ( P \Rightarrow R \right ) \vee \left ( Q \Rightarrow R \...
1
vote
4answers
41 views

Showing that $(A \land B)' \land (C' \land A)' \land (C \land B')' \to A'$ without a truth table

Problem: Prove that $(A \land B)' \land (C' \land A)' \land (C \land B')' \to A'$. What I have done so far: $(A \land B)'$ premise $(C' \land A)'$ premise $(C \land B')'$ premise $A' \lor B'$ 1, ...
1
vote
2answers
32 views

Proofs Using Tautologies

Let's say I want to formally prove a statement of the form $$p \implies q$$ So I do a bit of work,some re-arranging and eventually I arrive at a statement of the form $$p \implies p$$ which is a ...
2
votes
3answers
108 views

Logic Behind Epsilon-Delta Proofs (Single-Variable Calculus)

Most of what I am asking is based off this (fairly popular) article I've read here : https://bobobobo.wordpress.com/2008/01/20/how-to-do-epsilon-delta-proofs-1st-year-calculus/, but most lecturers, ...
0
votes
1answer
111 views

Progressing in Propositional Logic

I am self-studying precalculus-level mathematics in perhaps a more formal way than usual, which means that I am reading about logic, sets, proofs, etc. The text I am looking at contains as an example ...
1
vote
1answer
24 views

Resolution proof involving more than a literal

I want to show that the following clauses are unsatisfiable together using resolution (i.e. obtain a refutation): 1: $\lnot P_1 \lor \lnot P_2$ 2: $P_2 \lor \lnot P_3$ $P_1 \land P_3$ I perform ...
2
votes
1answer
16 views

conditional proposition vs biconditional proposition

So I have been working on college and am currently in a math class. The following question came up and I chose "->" as the answer. This was marked wrong and I challenged the answer but was told this ...
0
votes
2answers
38 views

finding a formula for a given truth table

How would one proceed in finding a formula from a given truth table without resort to the use of disjunctive normal form and karnaugh maps? For example, given ...
0
votes
1answer
24 views

Equivalence classes in the logical equivalence on some finite set of propositional formulas

I'm having trouble understanding the following problem: Let $S_n$ be the set of all formulas that can be built up with the atoms $\{A_1,...,A_n\}$. How many equivalence classes does the ...
2
votes
1answer
37 views

Q: Is the set of all binary connectives having an even number of Truth in their truth table is functionally incomplete?

Is the set $TC$ of all binary connectives having an even number of Truth values assigned to the entries of their truth table (i.e. 0, 2 or 4) is functionally incomplete? It's easy to see that the ...
1
vote
2answers
27 views

Does the fact that a modal operator distributive over disjunction imply that a modal operator is distributive over conjunction?

If L is an arbitrary operator on two propositions p and q: Does L(p $\vee$ q) $\Rightarrow$ Lp $\vee$ Lq imply L(p $\land$ q) $\rightarrow$ Lp $\land$ Lq?
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
21 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
55 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
52 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
62 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
71 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
24 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
43 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
28 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 ...
0
votes
1answer
71 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
66 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
179 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
40 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
164 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
37 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
88 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 ...