0
$\begingroup$

i hope you're all doing well. I was reading a paper recently that started out with a language $L$ with a set $PV$ of propositional variables, Boolean connectives $\neg, \vee$, and some modalities called $\Box$ and O.

It then says "$\wedge, \rightarrow,$ and $\leftrightarrow$ are defined in terms of $\neg$ and $\vee$." What do they mean? I understand that $\{\neg, \vee\}$ is a complete set of connectives, i.e. that any wff in propositional logic using any of the symbols $\neg, \vee, \wedge, \rightarrow,$ and $\leftrightarrow$ is tautologically equivalent to a wff just using $\neg$ and $\vee$.

So, do they mean that they consider $\rightarrow$ not as a boolean connective in its own right, but a notational abbreviation for using $\neg$ and $\vee$? i.e. $p \rightarrow q$ as an abbreviation for $\neg p \vee q$? (I understand that the two formulas are not literally equivalent if we consider classical propositional logic, where $\rightarrow$ is a distinct symbol from $\neg$ and $\vee$, and that the two formulas are merely tautologically equivalent.) Is it a common thing in logic papers to "abbreviate" like this? Thank you for any help/wisdom.

Sincerely,

Vien

p.s. here's the source. It's in the first paragraph of "Basic Definitions" if that helps at all. http://individual.utoronto.ca/philipkremer/onlinepapers/DTL.pdf Cheers!

$\endgroup$
3
$\begingroup$

"Do they mean that they consider $\to$ not as a boolean connective in its own right, but a notational abbreviation for using $\neg$ and $\lor$?" Yes (probably).

It is pretty common to initially introduce a restricted formal language $L$, and then later want -- for readability, for convenience -- to be able to use devices not in the ground language $L$. We can go two ways. (a) We can officially move to a less restricted language $L'$ by adding new vocabulary and rules for dealing with it in $L'$. Or (b) we can stick strictly to $L$ but allow ourselves street slang in writing sentences of $L$ -- so e.g. we allow ourselves to write $(p \to q)$ as causal unofficial argot for $(\neg p \lor q)$, but $\to$ isn't really part of our official formal language. It really makes little odds which line we take in most cases, but (b) is clean and used in many logic texts and probably what is intended here.

$\endgroup$
  • 1
    $\begingroup$ And (b) is more convenient if we want to make arguments based on the actual structure of formulae, e.g., induction over the complexity of a formula. $\endgroup$ – Brian M. Scott Jul 10 '13 at 10:22
0
$\begingroup$

Very few authors use all 16 two-valued or "Boolean" connectives in their own right. You might find an exception in St. Lesniewiski's work who had an excellent notation for binary and unary "Boolean" connectives and had specific symbols for all of them. By excellent, I mean that in a glance you could tell his notational system came as comprehensive for all 16 connectives, and as long as you knew the basic principles of his notation, you could figure out what each symbol meant. So, in principle, you don't have to remember much to understand the notation. Unfortunately, I don't know how to present those symbols typographically here.

Also, even though plenty of authors do use $\rightarrow$ or some other symbol as an abbreviation, others just use it as a primitive connective.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.